代码随想录 day 17 二叉树

第六章 二叉树 part05

详细布置

654.最大二叉树

又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历
题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

617.合并二叉树

这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。
题目链接/文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

700.二叉搜索树中的搜索

递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性
题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html
视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

98.验证二叉搜索树

遇到 搜索树，一定想着中序遍历，这样才能利用上特性。
但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。
题目链接/文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

654.最大二叉树

题目链接

https://leetcode.cn/problems/maximum-binary-tree/description/

解题思路

分析题目即可解出代码，
开始每次都重建了数组，优化后的代码一直复用同一个数组，递归函数加入子数组的范围下标即可。

code

public TreeNode constructMaximumBinaryTree(int[] nums) {
        return recursion(nums,0,nums.length-1);
    }
    //复用一个数组，根据索引下标切割子数组
    public TreeNode recursion(int[] nums,int left,int right){
        if(nums.length==0||left>right){
            return null;
        }
        //找到最大值作为根节点
        int index=0;
        int maxValue=Integer.MIN_VALUE;
        for(int i=left;i<=right;i++){
            if(nums[i]>maxValue){
                maxValue=nums[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(maxValue);
        root.left=recursion(nums,left,index-1);
        root.right=recursion(nums,index+1,right);
        return root;
    }

        //每次重建数组
        public TreeNode constructMaximumBinaryTree2(int[] nums) {
        if(nums.length==0){
            return null;
        }
        //找到最大值作为根节点
        int index=0;
        int maxValue=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>maxValue){
                maxValue=nums[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(maxValue);
        int[] leftNums=new int[index];
        System.arraycopy(nums,0,leftNums,0,leftNums.length);
        int[] rightNums=new int[nums.length-1-leftNums.length];
        System.arraycopy(nums,leftNums.length+1,rightNums,0,rightNums.length);
        root.left=constructMaximumBinaryTree(leftNums);
        root.right=constructMaximumBinaryTree(rightNums);
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

617.合并二叉树

题目链接

https://leetcode.cn/problems/merge-two-binary-trees/description/

解题思路

使用前序遍历合并
递归终止条件就是 俩颗树遍历都为null了，其中一个为null返回另一个都不需要继续向下递归了。
中条件就是 俩颗树的值相加，生成一个新节点，这个新节点可以复用root1的树，在root1这棵树上变化。

code

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //1.递归终止条件，都为null  都遇到了空节点返回null
        if(root1==null&&root2==null){
            return null;
        }
        //root1是null 子树就是root2了不需要在递归了
        if(root1==null){
            return root2;
        }
        //root2是null 子树就是root1了不需要在递归了
        if(root2==null){
            return root1;
        }
        //TreeNode root=new TreeNode(root1.val+root2.val);//中
        //复用root1的树
        root1.val+=root2.val;
        root1.left=mergeTrees(root1.left,root2.left);//左
        root1.right=mergeTrees(root1.right,root2.right);//右
        return root1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

700.二叉搜索树中的搜索

题目链接

解题思路

二叉搜索树的概念：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树
解题注意点：
不要忘了 递归函数还有返回值。
递归函数的返回值是什么? 是 左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。
所以要 res = searchBST(root->left, val)
最后返回res

code

    public TreeNode searchBST(TreeNode root, int val) {
        //节点为null 没找到
        if(root==null){
            return root;
        }
        //找到节点返回
        if(root.val==val){
            return root;
        }
        //记录递归结果 返回
        TreeNode res=null;
        if(root.val>val){
            res=searchBST(root.left,val);
        }else if(root.val<val){
            res=searchBST(root.right,val);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

98.验证二叉搜索树

题目链接

https://leetcode.cn/problems/validate-binary-search-tree/description/

解题思路

二叉搜索树 中序遍历单调递增，根据这个特性解题
定义前一个节点的指针，如果前一个节点大于等于当前节点，则不符合单调递增，则不是二叉搜索树

code

    //二叉搜索树 中序遍历单调递增
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean left=isValidBST(root.left);
        if(pre!=null && pre.val>=root.val){
            return false;
        }else{
            pre=root;
        }
        boolean right=isValidBST(root.right);
        return left&&right;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14