代码随想录训练营第十七天| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

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;}
}