654. 最大二叉树

题目来源：LeetCode 654

通过递归方法构建二叉树，每次在指定区间内找到最大值作为根节点，然后递归构建左右子树。

时间复杂度： O(n²)（最坏情况下）
空间复杂度： O(n)

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

    private TreeNode buildMaxTree(int[] arr, int l, int r) {
        if (l > r) return null;
        int maxPos = findMaxIndex(arr, l, r);
        TreeNode node = new TreeNode(arr[maxPos]);
        node.left = buildMaxTree(arr, l, maxPos - 1);
        node.right = buildMaxTree(arr, maxPos + 1, r);
        return node;
    }

    private int findMaxIndex(int[] arr, int start, int end) {
        int idx = start;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] > arr[idx]) idx = i;
        }
        return idx;
    }
}

617. 合并二叉树

题目来源：LeetCode 617

递归合并两棵二叉树，对应节点值相加。如果某棵树的节点为空，则直接返回另一棵树的节点。

时间复杂度： O(min(m, n))
空间复杂度： O(min(m, n))

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

注意：上述代码进行了简化，原递归逻辑通过条件判断提前返回，减少了嵌套分支。

700. 二叉搜索树中的搜索

题目来源：LeetCode 700

利用二叉搜索树性质，通过比较节点值与目标值实现二分查找。

时间复杂度： O(h)，h为树高
空间复杂度： O(h)

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);
        return searchBST(root.right, val);
    }
}

98. 验证二叉搜索树

题目来源：LeetCode 98

利用中序遍历得到递增序列的特性进行验证。以下为两种实现方式：

方法一：全局变量标记

class Solution {
    private TreeNode prev;
    private boolean valid;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        valid = true;
        inorderCheck(root);
        return valid;
    }

    private void inorderCheck(TreeNode node) {
        if (node == null || !valid) return;
        inorderCheck(node.left);
        if (prev != null && node.val <= prev.val) {
            valid = false;
            return;
        }
        prev = node;
        inorderCheck(node.right);
    }
}

方法二：递归直接返回结果

class Solution {
    private TreeNode previous;

    public boolean isValidBST(TreeNode root) {
        previous = null;
        return validateTree(root);
    }

    private boolean validateTree(TreeNode node) {
        if (node == null) return true;
        if (!validateTree(node.left)) return false;
        if (previous != null && node.val <= previous.val) return false;
        previous = node;
        return validateTree(node.right);
    }
}

两种方法核心思想相同，均通过中序遍历比较前后节点值。方法一通过全局布尔变量控制，方法二则直接通过递归返回值判断。