算法训练营Day20

2023-12-18 17:19:29

654.最大二叉树

654. 最大二叉树 - 力扣（LeetCode）

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

617.合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

体会一下递归操作两棵二叉树。

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. 二叉搜索树中的搜索 - 力扣（LeetCode）

二叉搜索树特点：

左孩子小于根节点，右孩子大于根节点

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

根据特点优化

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

        if(val<root.val){
            return searchBST(root.left,val);
        }else{
            return searchBST(root.right,val);
        }
    }
}

利用BST特点迭代，不需要栈

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

?98.验证二叉搜索树?

98. 验证二叉搜索树 - 力扣（LeetCode）

遇到?搜索树，一定想着中序遍历，这样才能利用上特性。?

但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。

就是不能单纯的比较root》left? root<right，比较的时候可以采用指针的方式，注意指针定义到递归外面，整体判断是先判断左孩子和根节点是true，再判断根节点和有孩子是true，都为true这个树才是true。做递归题的时候，先按照单层逻辑写下来再看整体的具体递归的逻辑，方便思考，不然会一入递归深似海啊~

class Solution {
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root==null)return true;
        boolean left = isValidBST(root.left);
        if(pre!=null&&pre.val>=root.val){
            return false;
        }
        pre = root;
        boolean right = isValidBST(root.right);
        return left&&right;
    }
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135057095
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。