Day17补代码随想录 654.最大二叉树|617.合并二叉树|700.二叉搜索树中的搜索|98.验证二叉搜索树

654.最大二叉树

题目

【体会为什么构造二叉树都是前序遍历】

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 *nums 构建的 * **最大二叉树 ** 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

思路

终止条件：
- 数组大小=1时，是叶子节点，也可能是根节点
- 需要对数组为null的情况进行判断，因为题目给了数组大小>=0
前序遍历
- 中
 - 遍历数组，如果数组中的元素>最大值，更新最大值，并定位index
- 遍历数组，如果数组中的元素>最大值，更新最大值，并定位index
- 左
 - index>0时，取左前序，[0,index) (左闭右开)
- index>0时，取左前序，[0,index) (左闭右开)
- 右
 - index<numsize-1，取右前序，[index+1,numsize)
- index<numsize-1，取右前序，[index+1,numsize)

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maximumBinaryTree(nums,0,nums.length);

    }
    public TreeNode maximumBinaryTree(int[] nums,int leftIndex,int rightIndex){
        //终止条件，如果叶子节点<1时,递归到尽头，区间[leftIndex,rightIndex)没有元素了。
        if(rightIndex-leftIndex<1){
            return null;
        }
        //只有一个元素,返回单个节点
        if(rightIndex-leftIndex==1){
            return new TreeNode(nums[leftIndex]);
        }
        //最大值value和index
        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);
        //左 区间[leftIndex,rightIndex)
        root.left=maximumBinaryTree(nums,leftIndex,maxIndex);
        //右 区间[maxIndex+1,rightIndex);
        root.right=maximumBinaryTree(nums,maxIndex+1,rightIndex);
        return root;
    }
}

总结

终止条件有2个，节点<1，返回null，节点=1，返回1个节点
前序遍历的递归要设置好变化的区间，[)左闭右开
更新中的时候for(int i=leftIndex+1;i<rightIndex;i++){，起始遍历是int i=leftIndex+1，因为最开始的基准值maxValue即为i=0的值

617.合并二叉树

题目

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

思路

Carl

返回值是处理完的根节点，参数是两个二叉树的节点
终止条件
- 同步遍历
  - tree1==null return tree2;
  - tree2==null return tree1;
  - tree1,tree2都为空 null
代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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.二叉搜索树中的搜索

题目

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

思路

二叉搜索树，根节点比所有的左子树节点都要大，比所有的右子树节点都要小。
终止条件
- 节点为null||节点=val return root;

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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;  
    }
}

前序遍历

思路

前序遍历
- 中，终止条件中
- 左
- 右
- 返回result

98.验证二叉搜索树

题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树

只包含** 小于 **当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在 [1, 104] 内
-231 <= Node.val <= 231 - 1

思路

中序遍历后存到数组中，看看是否是【单调递增】的。
伪代码
- 终止条件 root==null，true
- 左递归再判断，如果左子树不满足条件的话，没必要继续右子树了
- 中 root<=max.val
 - 更新指针，max=root;
- 右
 - 递归，不用判断，因为到右的时候已经最后了。
 - 最后的返回值即右的返回值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = 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;  
    }
}