day19

1、654 最大二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length);
    }

    public TreeNode traversal(int[] nums, int left, int right){//左闭右开
        if(left >= right){
            return null;
        }

        int maxIndex = left;
        for(int i=left+1; i<right; i++){
            if(nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        } 

        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = traversal(nums, left, maxIndex);
        root.right = traversal(nums, maxIndex+1, right);

        return root;
    }
}

2、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;
    }
}

3、700 二叉搜索树中的搜索

1. 递归

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

2. 迭代

   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 root;
       }
   }
   
   

4、98 验证二叉搜索树

class Solution {
    long preVal = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }

        // 访问左子树
        if(!isValidBST(root.left)){
            return false;
        }

        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if(root.val <= preVal){
            return false;
        }
        preVal = root.val;

        // 访问右子树
        return isValidBST(root.right);
    }
}