654.最大二叉树
题目链接/文章讲解： 代码随想录视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftindex, int rightindex){if(rightindex - leftindex < 1){//没有元素return null;}if(rightindex - leftindex == 1){//只有一个元素return new TreeNode(nums[leftindex]);}int maxindex = leftindex;//最大值所在的位置int maxval = nums[maxindex];///最大值for(int i = leftindex + 1; i < rightindex; i++){if(nums[i] > maxval){maxval = nums[i];maxindex = i;}}TreeNode root = new TreeNode(maxval);//根据maxindex划分左右子树root.left = constructMaximumBinaryTree1(nums, leftindex, maxindex);root.right = constructMaximumBinaryTree1(nums, maxindex + 1, rightindex);return root;}
}617.合并二叉树
题目链接/文章讲解：代码随想录
视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili
- 确定递归函数的参数和返回值：
- 确定终止条件：
- 确定单层递归的逻辑：
Java代码：
class Solution {//递归public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}class Solution{public TreeNode mergeTrees(TreeNode root1, TreeNode root2){//使用栈迭代if(root1 == null) return root2;if(root2 == null) return root1;Stack<TreeNode> stack = new Stack<>();stack.push(root2);stack.push(root1);while(!stack.isEmpty()){TreeNode node1 = stack.pop();TreeNode node2 = stack.pop();node1.val += node2.val;if(node2.right != null && node1.right != null){stack.push(node2.right);stack.push(node1.right);}else{if(node1.right == null){node1.right = node2.right;}}if(node2.left != null && node1.left !=null){stack.push(node2.left);stack.push(node1.left);}else{if(node1.left == null){node1.left = node2.left;}}}return root1;}
}700.二叉搜索树中的搜索
题目链接/文章讲解: 代码随想录
视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili
递归和迭代都可以 二叉搜索树是左子节点小于根节点 右子节点大于根节点
递归：
- 确定递归函数的参数和返回值
- 确定终止条件 如果root为空，或者找到这个数值了，就返回root节点。
- 确定单层递归的逻辑：因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
-
如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
重点在于应用二叉搜索树有序的特点
Java代码：（对每个东西要理解透彻）
class Solution {public TreeNode searchBST(TreeNode root, int val) {//递归if(root == null || root.val == val){return root;}TreeNode left = searchBST(root.left,val);if(left != null){return left;}return searchBST(root.right, val);}
}
class Solution{public TreeNode searchBST(TreeNode root, int val){if(root == null || root.val == val){return root;}if(val < root.val){return searchBST(root.left, val);}else{return searchBST(root.right, val);}}
}
class Solution{//迭代 普通二叉树public TreeNode seachBST(TreeNode root, int val){if(root == null || root.val == val){return root;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();if(node.val == val){return node;}if(node.right != null){stack.push(node.right);}if(node.left != null){stack.push(node.left);}}return null;}
}
class Solution{public TreeNode searchBST(TreeNode root,int val){while(root != null){if(val < root.val) root = root.left;else if(val > root.val) root = root.right;else return root;}return null;}
}98.验证二叉搜索树
题目链接/文章讲解： 代码随想录视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
这道题目比较容易陷入两个陷阱：
- 陷阱1
不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
写出了类似这样的代码：
if (root->val > root->left->val && root->val < root->right->val) {return true;
} else {return false;
}
我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。所以以上代码的判断逻辑是错误的。
节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！
- 陷阱2
样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。
此时可以初始化比较元素为longlong的最小值。
问题可以进一步演进：如果样例中根节点的val 可能是longlong的最小值 又要怎么办呢？文中会解答。
了解这些陷阱之后我们来看一下代码应该怎么写：
递归三部曲：
- 确定递归函数，返回值以及参数
要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中有int最小值，所以定义为longlong的类型，初始化为longlong最小值。
注意递归函数要有bool类型的返回值， 我们在二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？ (opens new window)中讲了，只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值。
其实本题是同样的道理，我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。
代码如下：
long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
bool isValidBST(TreeNode* root)
- 确定终止条件
如果是空节点 是不是二叉搜索树呢？
是的，二叉搜索树也可以为空！
代码如下：
if (root == NULL) return true;
- 确定单层递归的逻辑
中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。
只要把基本类型的题目都做过，总结过之后，思路自然就开阔了 ！
Java代码：
class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {if(root == null) return true;//左boolean left = isValidBST(root.left);if(!left) return false;//中if(max != null && root.val <= max.val) return false;max = root;//右boolean right = isValidBST(root.right);return right;}
}
class Solution{public boolean isValidBST(TreeNode root){if(root == null) return true;Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while(root != null || !stack.isEmpty()){while(root != null){stack.push(root);root = root.left;//左}//中TreeNode node = stack.pop();if(pre != null && node.val <= pre.val){return false;}pre = node;root = node.right;//右侧}return true;}
}
