算法训练营day18 | {654.最大二叉树, 617.合并二叉树, 700.二叉搜索树中的搜索, 98.验证二叉搜索树}

第六章二叉树part05，利用二叉搜索树的特性分析递归三步曲。

654. 最大二叉树

• 题目链接：654.最大二叉树
• 文档讲解：代码随想录–654.最大二叉树
• 视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树
• 状态：与106类似，递归的时候没有必要构造新数组，建议操作下标。

1.1 解题分析

• 分析递归三步曲：

  1. 参数和返回值是什么？ 要传入一个nums数组，当前递归区间的起点&终点，返回一个当前子树的根节点TreeNode。
  2. 确定递归的终止条件。 如果当前区间长度==0，return null; 如果当前区间长度==1，return 构造好的节点；
  3. 确定单层递归的逻辑。 构造二叉树的题目，必须采用中左右的顺序，先构造出根节点（适合前序遍历语义）。

• 前序遍历–递归法（数组区间左闭右闭）

  ▶

  654. 最大二叉树

  class Solution {
      public TreeNode constructMaximumBinaryTree(int[] nums) {
          return construct(nums, 0, nums.length - 1);
      }
  
      public TreeNode construct(int[] nums, int left, int right) {
          if(left > right) return null;
          if(left == right) return new TreeNode(nums[left]);
          int maxIndex = 0;
          int maxVal = 0;
          for (int i = left; i <= right; i++) {
              if (nums[i] > maxVal) {
                  maxVal = nums[i];
                  maxIndex = i;
              }
          }
          TreeNode root = new TreeNode(maxVal);
          root.left = construct(nums, left, maxIndex - 1);
          root.right = construct(nums, maxIndex + 1, right);
          return root;
      }
  }

617. 合并二叉树

• 题目链接：617. 合并二叉树
• 文档讲解：代码随想录–617.合并二叉树
• 视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树
• 状态：感觉适合自顶向下的操作，前序遍历。

2.1 解题分析

• 注意：

  • 同步遍历过程中，如果其中有一个节点已经遍历到null，此时return的是另一个二叉树的结点（带它的子树），且作为终止条件。
  • 直接操作tree1 或 重新定义一个二叉树，第一种方式空间复杂度更低。

• 前序遍历–递归法

  ▶

  617. 合并二叉树

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

700. 二叉搜索树中的搜索

• 题目链接：700.二叉搜索树中的搜索
• 文档讲解：代码随想录–700.二叉搜索树中的搜索
• 视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索
• 状态：Binary Search Tree，二叉搜索树是一个有序树，符合左<根<右的特性。

3.1 递归法

• 分析递归三步曲：
  1. 参数和返回值是什么？ 参数和leetcode给的一样，返回找到的节点；
  2. 确定递归的终止条件。 如果当前遍历到的节点为空，或者找到了目标值对应的节点，return该节点；
  3. 确定单层递归的逻辑。 本题如果采用递归法，属于有返回值的递归函数，那么父递归要基于子递归返回的结果进行判断，需定义一个临时变量接住这个结果。

▶

700. 二叉搜索树中的搜索

class Solution {
   public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        TreeNode result = null;
        if(val < root.val) result = searchBST(root.left, val);
        if(val > root.val) result = searchBST(root.right, val);
        return result;
    }
}

3.2 迭代法

二叉搜索树的迭代法比普通二叉树要简单很多，因为本身就是一个有序树，不需要回溯的过程，节点的有序性已经帮我们确定了搜索的方向。

▶

700. 二叉搜索树中的搜索

class Solution {
   public TreeNode searchBST(TreeNode root, int val) {
        while(root != null) {
            if (root.val == val) return root;
            else if (root.val > val) root = root.left;
            else root = root.right;
        }
        return null;
    }
}

98. 验证二叉搜索树

• 题目链接：98. 验证二叉搜索树
• 文档讲解：代码随想录–98.验证二叉搜索树
• 视频讲解：
• 状态：在中序遍历下，输出的二叉搜索树节点的数值是有序序列。

4.1 解题分析

• 利用BST中序遍历后有序递增的特性，验证一个树是否是有效二叉搜索树可以转化为判断中序遍历后的元素是否严格递增。

• 分析递归三步曲：

  1. 参数和返回值是什么？ 要传入一个根节点，返回boolean类型。此外还需要一个全局的变量不断更新最大值，和目前递归到的元素进行比较。
  2. 确定递归的终止条件。 遍历到节点为空时，返回true
  3. 确定单层递归的逻辑。 中序遍历，左中右，父递归要接住子递归的返回值，并且如果为false，不用再继续遍历了。当前层操作是比较遍历到的节点值是否比maxVal大。

• 中序遍历-递归（有全局变量）

  ▶

  98. 验证二叉搜索树

  class Solution {
      private Long maxVal = Long.MIN_VALUE;
  
      public boolean isValidBST(TreeNode root) {
          if (root == null) return true;
          if (!isValidBST(root.left)) return false;
          if (root.val <= maxVal) return false;
          maxVal = (long) root.val;
          return isValidBST(root.right);
      }
  }

• 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。这启示我们可以定义一个递归函数helper(root, lower, upper)来递归判断，函数表示以root为根的子树，判断子树中所有节点的值是否都在(l, r)的范围内。符合前序遍历的语义。

• 前序遍历-递归（无全局变量）

  ▶

  98. 验证二叉搜索树

  public boolean isValidBST(TreeNode root) {
          return helper(Long.MIN_VALUE, root, Long.MAX_VALUE);
      }
  
      public boolean helper(long lower, TreeNode root, long upper) {
          if (root == null) return true;
          if (!(lower < root.val && root.val < upper)) return false;
          if (!helper(lower, root.left, root.val)) return false;
          return helper(root.val, root.right, upper);
      }

4.2 关于递归函数什么时候需要一个全局变量

• 这道BST题，为什么需要全局变量？

  1. 因为通过中序遍历验证BST的正确性，本质上是把一个树拉平成一个递增序列，我在做的是一次线性扫描，而不是独立的子问题。
  2. 换句话说，序列的前一个元素不属于任何一个子树，而是属于遍历过程本身，所以需要借助外部的全局变量。返回值无法携带这份信息，或者说携带起来很别扭：

     class Result {
      boolean isValid;
      long maxVal;
     }

• 递归类型1：信息只向上返回（不需要全局变量）

  • 特点：子问题算完，只把结果返回给父节点，父节点不关心子节点之外的历史。
  • 典型例子：最大深度/是否平衡二叉树/是否对称

• 递归类型2：信息要在兄弟子树之间共享（需要全局变量）

  • 例如本题，root需要知道左子树已经访问过的最后一个值。

• 相反，解法二上下界法每一层的信息完整，不需要共享历史，不因此不用定义全局变量。

5. 今日收获

• 递归形参的语义是什么？形参=父问题给子问题的约束，每个子树是自洽的独立问题。
• 关于什么时候需要定义全局变量？子树之间需要共享历史，不属于任何一个独立的子问题时。
• 今天引入了二叉搜索树，与普通二叉树不同的有序特性要好好思考利用，就和之前的完全二叉树特性一样，往往是解题的关键。
• 学习时长：3小时