算法训练（leetcode）二刷第十五天 | 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树

654. 最大二叉树

leetcode题目地址

递归建树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] nums, int left, int right){// 左右闭区间if(right<left) return null;int maxIdx = left;for(int i=left+1; i<=right; i++){if(nums[i]>nums[maxIdx]) maxIdx=i;}TreeNode root = new TreeNode(nums[maxIdx]);root.left = buildTree(nums, left, maxIdx-1);root.right = buildTree(nums, maxIdx+1, right);return root;}public TreeNode constructMaximumBinaryTree(int[] nums) {return buildTree(nums, 0, nums.length-1);}
}

617. 合并二叉树

leetcode题目地址

同上题，递归建树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode getResultTree(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null) return null;TreeNode node = new TreeNode();// 左空右不空if(root1 == null) {node.val = root2.val;node.left = getResultTree(root1, root2.left);node.right = getResultTree(root1, root2.right);return node;} else if(root2 == null) {// 左不空右空node.val = root1.val;node.left = getResultTree(root1.left, root2);node.right = getResultTree(root1.right, root2);return node; }else{node.val = root1.val + root2.val;node.left = getResultTree(root1.left, root2.left);node.right = getResultTree(root1.right, root2.right);return node; }}public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return getResultTree(root1, root2);}
}

700. 二叉搜索树中的搜索

leetcode题目地址

二叉搜索树中进行搜索就是一个二分查找的过程。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(root.val == val){return root;}    if(root.val > val) return searchBST(root.left, val);return searchBST(root.right, val);}
}

98. 验证二叉搜索树

leetcode题目地址

二叉搜索树的中序遍历序列是单调递增的，因此借助中序遍历，若出现后一个元素小于前一个元素则为false。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

写法一

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private TreeNode pre;private boolean flag;public void inOrder(TreeNode root){if(!this.flag) return;if(root.left != null) inOrder(root.left);if(pre!=null && root.val <= pre.val) flag = false;pre = root;if(root.right != null) inOrder(root.right);}public boolean isValidBST(TreeNode root) {this.pre = null;this.flag = true;if(root == null) return true;inOrder(root);return this.flag;}
}

写法二

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private TreeNode pre;public boolean inOrder(TreeNode root){if(root == null) return true;// 左boolean left = inOrder(root.left);if(!left) return false;// 中if(pre != null && root.val<=pre.val) return false;pre = root;// 右boolean right = inOrder(root.right);if(!right) return false;return true;}public boolean isValidBST(TreeNode root) {this.pre = null;if(root == null) return true;return inOrder(root);}
}