🎈LeetCode654.最大二叉树

链接：654.最大二叉树

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

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

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

还是用递归三部曲做，代码如下：

java">public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 1 <= nums.length <= 1000
        return bulid(nums,0,nums.length-1);
    }
    public TreeNode bulid(int[] nums,int start,int end){
        // 0 <= nums[i] <= 1000
        if(start>end){
            return null;
        }
        if(start==end){
            return new TreeNode(nums[start]);
        }
        int max=0;
        int index=0;
        for(int i=start;i<=end;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(max);
        root.left=bulid(nums,start,index-1);
        root.right=bulid(nums,index+1,end);
        return root;
    }

🎈LeetCode617.合并二叉树

链接：617.合并二叉树

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

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

返回合并后的二叉树。

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

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

🎈LeetCode700. 二叉搜索树中的搜索

链接：700.二叉搜索树中的搜索

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

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

java">public TreeNode searchBST(TreeNode root, int val) {
        //root 是二叉搜索树 
        if(root==null){
            return null;
        }
        TreeNode node=new TreeNode(0);
        if(root.val>val){
           node=searchBST(root.left,val);
        }else if(root.val<val){
            node=searchBST(root.right,val);
        }else{
            return root;
        }
        return node;
    }

🎈LeetCode98. 验证二叉搜索树

链接：98.验证二叉搜索树

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

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

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

二叉搜索树的中序遍历正好是一个递增的序列，可以利用中序遍历来判断是不是二叉搜索树，代码如下：

java">public TreeNode searchBST(TreeNode root, int val) {
        //递归法
        //root 是二叉搜索树 
        if(root==null){
            return null;
        }
        TreeNode node=new TreeNode(0);
        if(root.val>val){
           node=searchBST(root.left,val);
        }else if(root.val<val){
            node=searchBST(root.right,val);
        }else{
            return root;
        }
        return node;
    }

java">public boolean isValidBST(TreeNode root) {
        // 迭代法
        if(root==null){
            return true;
        }
        Stack<TreeNode> st=new Stack<>();
        st.push(root);
        TreeNode pre=null;
        while(!st.isEmpty()){
            TreeNode node=st.peek();
            if(node!=null){
                st.pop();
                if(node.right!=null){
                    st.push(node.right);
                }
                st.push(node);
                st.push(null);
                if(node.left!=null){
                    st.push(node.left);
                }
            }else{
                st.pop();
                TreeNode temp=st.pop();
                if(pre!=null && pre.val>=temp.val){
                    return false;
                }
                pre=temp;
            }
        }
        return true;
    }