代码随想录算法训练营 DAY 20 | 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654.最大二叉树

• 凡是构造二叉树类的题 都要用前序遍历 中左右（一定要先构造出根节点，才能构造左子树右子树）
  1. 确定递归函数

  public TreeNode constructMaximumBinaryTree(int[] nums)
  

  根据传入的这个数组，构造二叉树（左右子树的时候数组会变的）

  
  （图片来源网络，侵删）
  1. 递归终止条件

  当数组大小==1时，说明到了叶子节点。（题目要求数组大小>=1，不考虑空的情况）

  if(nums.length==1) 
  	return new TreeNode(nums[0]);
  

  1. 单层逻辑

  要找到数组里的最大值以及下标。要根据下标对数组进行分割。

  
  （图片来源网络，侵删）

  //以下是 中 的逻辑
  int maxValue = 0;
  int index = 0;
  for(int i = 0; i  maxValue) {
  		maxValue = nums[i];
  		index = i;
  	}
  }
  node = new TreeNode(maxValue);
  

  先构造左子树，需要分割数组。至少保证左/右区间里有1个元素！

  //左
  if(index > 0) {
      int[] newNum = newArray(0,index);  //分割左区间 定义新数组的函数 区间是左闭右开
      node.left = contract(newNum);
  }
  //右
  if(index  
  优化：
   
  每次把新的左右区间传入函数里，没必要创造新的数组。
   
  class Solution {
      public TreeNode construct(int[] nums, int left, int right) {
          if(right - left  maxVal) {
                  maxVal = nums[i];
                  maxIndex = i;
              }
          }
          TreeNode root = new TreeNode(maxVal);
          root.left = construct(nums,left,maxIndex);
          root.right = construct(nums, maxIndex+1,right);
          return root;
      }
      public TreeNode constructMaximumBinaryTree(int[] nums) {
          return construct(nums, 0, nums.length);
      }
  }
   
  617.合并二叉树

  • 怎么同时操作两个二叉树？前序遍历
    1. 递归函数返回值和参数

    TreeNode mergeTree(TreeNode root1, TreeNode root2)
    

    1. 确定终止条件

    操作两个二叉树的终止条件怎么写？

    两棵树同步进行遍历。如果一个为空，返回另一个树对应位置的节点

    if(root1 == null) return root2;
    if(root2 == null) return root1;
    //在上面已经包含了root1 root2同时为空的情况！（就是return null了）
    

    1. 单层递归逻辑

    我们直接在tree1的结构上改，不重新造一棵树了！

    //接下来是r1和r2都不为空的情况
    root1.value += root2.value; //中 
    root1.left = mergeTree(root1.left, root2.left);  //左
    root1.right = mergeTree(root1.right, root2.right);  //右
    return root1;
    

    本题前中后序都是可以的。

    • 完整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;
          }
      }
      

      700.二叉搜索树中的搜索

      • 明确二叉搜索树的性质：左孩子都比根节点小，右孩子都比根节点大

        //迭代法
        class Solution {
            public TreeNode searchBST(TreeNode root, int val) {
                while(root != null) {
                    if(val  root.val) root = root.right;
                    else return root;
                }
                return null;
            }
        }
        //递归法 注意非空和找到的情况，都返回root。左右递归的返回值统一用result接，最后return
        class Solution {
            public TreeNode searchBST(TreeNode root, int val) {
                if(root == null || val == root.val) return root;
                TreeNode result = null; 
                if(val  root.val) result = searchBST(root.right, val);
                return result;
            }
        }
        

        98.验证二叉搜索树

        • 二叉搜索树可以用中序遍历，这样遍历的结果就是有序数组了。

          直白想法：用中序遍历，存到数组里判断是否有序。

          优化：不用存到数组里，直接在递归遍历过程中比较！

          误区

          • 陷阱1

            不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。例如：

            if (root->val > root->left->val && root->val right->val)
            

            应该要满足左子树所有节点小于中间节点，右子树所有节点大于中间节点，这只满足了左右孩子！

            • 陷阱2

              样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

              此时可以初始化比较元素prev为long的最小值Long.MIN_VALUE

              • 左和右遍历 需要一个返回值left和right接住递归回来的结果。最后return left&& right。

                —相当于完成了陷阱1里没做到的！左子树和右子树

                class Solution {
                    long prev = Long.MIN_VALUE;
                    public boolean isValidBST(TreeNode root) {
                        if(root == null) return true;  //null树也是BST
                        boolean left = isValidBST(root.left);  //左
                        if(root.val > prev) { //中
                            prev = root.val;
                        }
                        else return false;
                        boolean right = isValidBST(root.right); //右
                        return left && right;
                    }
                }
                

                day20总结

                • 二叉搜索树 中序遍历 结果是有序的
                • 构造二叉树 用前序遍历