Day15 二叉树part05| LeetCode 654.最大二叉树，617.合并二叉树 ，700.二叉搜索树中的搜索，98.验证二叉搜索树

654.最大二叉树

654. 最大二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
   if(nums.length==1)//遍历到了叶子节点
            {
                    return new TreeNode(nums[0]);
            }

            int maxValue=nums[0];
            int maxIndex=0;
            for(int i=0;i<nums.length;i++)
            {
                if(nums[i]>maxValue)
                {
                    maxValue=nums[i];
                    maxIndex=i;
                }

            }
            TreeNode node=new TreeNode(maxValue);
            if(maxIndex>0)
            {
                int[] leftnums=new int[maxIndex];
                for(int i=0;i<maxIndex;i++)
                {
                    leftnums[i]=nums[i];
                }
                node.left=constructMaximumBinaryTree(leftnums);
            }
            if(maxIndex<nums.length-1)
            {
                int[] rightnums=new int[nums.length-maxIndex-1];
                int j=0;
                for(int i=maxIndex+1;i<nums.length;i++)
                {
                    rightnums[j]=nums[i];
                    j++;
                }
                node.right=constructMaximumBinaryTree(rightnums);
            }
           return node;
        }
    
}

617.合并二叉树

617. 合并二叉树

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. 二叉搜索树中的搜索

  class Solution {
        public TreeNode searchBST(TreeNode root, int val) {

            if(root==null||root.val==val)
                return root;

            TreeNode result=null;
            if(root.val<val) result=searchBST(root.right,val);
            if(root.val>val) result=searchBST(root.left,val);
            return result;
        }
    }

98.验证二叉搜索树

98. 验证二叉搜索树

• 有效的二叉搜索树
  • 节点的左子树只包含小于当前节点的值
  • 节点的右子树只包含大于当前节点的值
  • 所有左子树和右子树自身也必须是二叉搜索树
• 方法一：中序遍历，将二叉搜索树转变成一个数组，判断该数组是否递增，且元素不重复

 class Solution {
       public  List<Integer>  res = new ArrayList<>();
        void traversal(TreeNode root)
        {
            if(root==null) return ;

            traversal(root.left);s
            res.add(root.val);
            traversal(root.right);
        }

        public boolean isValidBST(TreeNode root) {

           traversal(root);
           for(int i=1;i<res.size();i++)
           {
               if(res.get(i)<=res.get(i-1))
                   return false;
               
               
           }
           return 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;

        }
    }