代码随想录算法训练营第十九天 | LeetCode 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
1. LeetCode 654. 最大二叉树
1.1 思路
- 对于这题我们要构造二叉树，凡是构造二叉树类的题目都要用前序遍历，“中左右”，先构造根节点，然后再是左子树右子树，左子树和右子树也是先“中左右”。
- 递归函数的参数和返回值：返回值就是这个二叉树的根节点，参数就是数组
- 终止条件：如果数组大小等于1说明到叶子节点了，就return new TreeNode(nums[0])。
- 单层递归的逻辑：找到数组的最大值及其下标，定义一个maxValue=0，index=0。遍历数组找到它们。找到最大值就定义新节点然后把数值放入，然后就是构造节点的左右子树
- 构造子树就要分割数组，因为终止条件是至少要有一个元素的。所以我们要判断左子树是否至少有一个元素（如果左子树没元素，说明就没有左子树咯），通过（index>0）来判断左子树是否至少有一个元素，有就切割数组，新的左子树数组就是[0,index)，左闭右开，包含左端点但不包含右端点，右端点是index的，是根节点不是左子树的。然后就是 node.left=函数(新的左子树数组)
- 右子树同理，至少有一个元素，理由同上，通过(index<nums.length-1)来判断右子树是否至少有一个元素，有就切割数组，新的右子树数组就是[index+1，nums.length)，因为是左闭右开区间，index是根节点的，不是右子树的，而右端点不包含，就可以是nums.length。然后就是node.right=函数(新的右子树数组)
- 最后return node就是二叉树的根节点
1.2 代码
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; } }
2. LeetCode 617. 合并二叉树
2.1 思路
- 这题考察同时操作两个二叉树的能力，这题递归的情况还是前序更方便些，也更直观
- 递归函数的参数和返回值：返回值就是合并后的二叉树的根节点，参数是一个是二叉树t1，一个是二叉树t2
- 终止条件：如果t1遍历到空就返回t2对应位置的节点，如果t2遍历到空就返回t1对应位置的节点
- 单层递归的逻辑：我们直接改t1的结构，就不创建新树了。t1.val+=t2.val。然后是递归t1.left=函数(t1.left, t2.left)；t1.right=函数(t1.right, t2.right)；最后return t1就是新的树了
- 如果要创建新树的话就把新树的节点的值为两树之和即可，终止条件是一样的
2.2 代码
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; } }
3. LeetCode 700. 二叉搜索树中的搜索
3.1 递归法思路
- 二叉搜索树中自带顺序，因此不强调前中后序。
- 确定递归函数的参数和返回值：返回的是对应值的节点，参数是节点和对应值
- 终止条件：如果遍历的节点是空或者就是对应数值的节点就return root。
- 单层递归的逻辑：创建新的变量节点result=null。如果要搜索的值比root.val小，说明在左子树，就result=函数(root.left, val)；果要搜索的值比root.val大，说明在右子树，就result=函数(root.right, val)；如果都没有就return result。这是个null
3.2 迭代法思路
- 通过while(root!=null)遍历
- 如果查找的值比root.val小就向左遍历，root=root.left
- 如果查找的值比root.val大就向右遍历，root=root.right
- 如果找到了就直接return root
- 如果退出循环就说明没找到，就return null
3.3 代码
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 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; } }
4. LeetCode 98. 验证二叉搜索树
4.1 思路
- 二叉搜索树的遍历最好是中序，因为二叉搜索树的特性“左中右”，先左再中后右就是一个有序的顺序，从小到大的顺序
- 递归函数的返回值和参数：返回值boolean，参数就是根节点
- 终止条件：如果root是null，就return true，因为空树也是二叉搜索树，同时也是完全二叉树、满二叉树、平衡二叉树
- 单层递归的逻辑：定义一个数组，左：函数(root.left)，中：把节点值放入数组，右：函数(root.right)，然后判断数组是否有序，有序说明是true否则就是false
- 更优解：不用创建数组。解题误区：单纯的比较左节点小于中间节点，右节点大于中间节点，这样不全面，我们要比左子树所有节点都大，比右子树所有节点都小
- 递归过程：返回值和参数、终止条件同上。定义一个全局变量long prev=Long.MIN_VALUE，表示最小值，因为这题会出现比Integer.MIN_VALUE还小的，只能创建个更小的才行了。
- 左：boolean left=函数(root.left)。如果root的值比prev大，prev就更新为root.val，prev就记录了当前节点的前一个节点的数值，因为中序遍历的root的值是递增的，prev就会持续小于root的值，这样root.val就始终比前一个节点大，如果root的值比prev小，这样就不是二叉搜索树了，就return false；
- 右：boolean right=函数(root.right)
- return left&&right。左右子树要同时符合条件这样才是符合题意的
- 如果这里采用前一个节点与后一个节点比较的方式的话，就需要创建一个max节点，初始化为null，如果max不为空并且max.val>=root.val，就返回false。否则就更新为root节点，这样作为记录root的前一个节点，因为root每次递归的时候都是下一个节点了，那么max就是root的前一个节点。这样可以不需要long prev初始化为最小值的方式
4.2 代码
// 简洁实现·中序遍历 class Solution { private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } if (root.val <= prev) { // 不满足二叉搜索树条件 return false; } prev = root.val; return isValidBST(root.right); } } 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; } }
