No.1

题目

最大二叉树

思路

• 递归法
• 注意保持区间定义一致[left, right)

递归分析

1. 返回值：节点，参数：数组，起点，终点
2. 终止逻辑：数组为空，返回空
3. 单层递归过程：找到该段数组最大值，根据其坐标，将数组分割为左和右，作为左子树和右子树

代码

public TreeNode constructHelper(int[] nums, int left, int right) {  
    // [left, right)  
    // 长度为0，返回空  
    if (right - left == 0)  
        return null;  
  
    // 长度为1，不用找最大值，直接返回TreeNode  
    if (right - left == 1)  
        return new TreeNode(nums[left]);  
  
    // 长度不为1，找到最大值坐标，分割数组  
    int maxIndex = left;  
    for (int i = left; i < right; i++)  
        maxIndex = nums[i] > nums[maxIndex] ? i : maxIndex;  
    TreeNode root = new TreeNode(nums[maxIndex]);  
  
    // -------- [leftLeft, leftRight), maxIndex, [rightLeft, rightRight) ------>  
    int leftLeft = left;  
    int leftRight = maxIndex;  
    int rightLeft = maxIndex + 1;  
    int rightRight = right;  
  
    root.left = constructHelper(nums, leftLeft, leftRight);  
    root.right = constructHelper(nums, rightLeft, rightRight);  
  
    return root;  
}  
  
public TreeNode constructMaximumBinaryTree(int[] nums) {  
    if (nums.length == 0)  
        return null;  
  
    return constructHelper(nums, 0, nums.length);  
}

No.2

题目

合并二叉树

思路

• 递归
• 问题：假如其中一个节点为null，我不想创建TreeNode，直接用另一个节点，是否会导致错误？
• 不会导致错误，而且必须这么做。因为后序还需要递归节点的左右子，假如创建了新的节点，那原来节点的孩子怎么办？一定会出错。所以除非在处理中间节点（因为会处理root.left root.right），处理左节点、右节点一定不能创建新的节点。
• 代码不复杂，但要考虑透彻

递归分析

1. 返回值：节点，参数：左节点，右节点
2. 终止逻辑：如果左子为null，那么返回右子（不管右子是不是null）；如果右子为null，那么返回左子（同样不管左子是不是null）
3. 单层递归过程：前序遍历，先处理中间节点，然后挂上左子树和右子树

代码

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {  
    if (root1 == null)  
        return root2;  
  
    if (root2 == null)  
        return root1;  
  
    // root1 != null && root2 != null  
    TreeNode root = new TreeNode(root1.val + root2.val);  
    root.left = mergeTrees(root1.left, root2.left);  
    root.right = mergeTrees(root1.right, root2.right);  
  
    return root;  
}

No.3

题目

二叉搜索树中的搜索

思路

• 找到值，如何在多层递归中返回对应的节点？通过return层层返回

递归分析

1. 返回值：节点，参数：节点，要找的值
2. 终止逻辑：找到符合的节点或节点为空，返回节点；
3. 单层递归过程：val比当前节点值大，就往右子树递归；val比当前节点值小，就往左子树递归；

代码

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.right, val);  
    if (val < root.val)  
        result = searchBST(root.left, val);  
  
    return result;  
}

No.4

题目

验证二叉搜索树

思路

• 递归
• 中序遍历下，输出的BST节点的数值是有序序列

递归思路

1. 返回值：void，参数：节点，节点值列表
2. 终止逻辑：节点为空，返回；
3. 单层递归过程：中序遍历，取当前节点值放到列表中

代码

public void inorderTraverse(TreeNode node, List<Integer> inorderBST) {  
    if (node == null)  
        return;  
  
    inorderTraverse(node.left, inorderBST);  
    inorderBST.add(node.val);  
    inorderTraverse(node.right, inorderBST);  
}  
  
public boolean isValidBST(TreeNode root) {  
    List<Integer> inorderBST = new ArrayList<>();  
    inorderTraverse(root, inorderBST);  
  
    for (int i = 1; i < inorderBST.size(); i++) {  
        if (inorderBST.get(i) <= inorderBST.get(i - 1))  
            return false;  
    }  
  
    return true;  
}