654.最大二叉树

654. 最大二叉树 - 力扣（LeetCode）
本题要注意区间问题，可以左闭右闭，也可以左闭右开，只是临界区间处理不同

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length-1);
    }
    // 左闭右闭区间
    private TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex < leftIndex) {
            return null;
        }
        if (rightIndex == leftIndex) {
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;
        int maxValue = nums[maxIndex];
        for (int i=leftIndex; i<=rightIndex; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxValue);
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex - 1);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

617.合并二叉树

617. 合并二叉树 - 力扣（LeetCode）
本题操作两个二叉树，将结果覆盖在root1上，如果root1为空，则覆盖为root2，反之相同

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）
本题在搜索二叉树中比普通二叉树容易，差别在于可以根据root.val与val的大小判断去左子树还是右子树，如果是普通二叉树，那么需要先在左子树搜索，没有的话再去右子树

# 普通二叉树
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        } 
        //先在左子树搜索，如果没有再去右子树
        TreeNode left = searchBST(root.left, val);
        if (left != null) {
            return left;
        }
        return searchBST(root.right, val);
    }
}
# 二叉搜索树
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        } 
        if (root.val < val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        } 

    }
}

98.验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）
二叉搜索树的中序遍历是递增的，所以可以中序遍历二叉树，得到一个数组，判断是否为二叉搜索树，但是这种方法效率比较低
更简单的方法就是在递增的时候就判断是否递增

class Solution {
    // 定义一个变量存前一个遍历的数据
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val <= prev) {
            return false;
        }
        prev = root.val;
        return isValidBST(root.right);
    }
}