BST 进阶：验证与恢复

验证二叉搜索树（LeetCode 98）

中序遍历递增 → 递归时传入合法区间 (min, max)：

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

迭代版（中序遍历同时验证）：

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    long prev = Long.MIN_VALUE;
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        if (cur.val <= prev) return false;
        prev = cur.val;
        cur = cur.right;
    }
    return true;
}

BST 迭代器（LeetCode 173）

next() 和 hasNext()，均摊 O(1) 时间，O(h) 空间（模拟中序遍历）：

class BSTIterator {
    private Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) { pushLeft(root); }

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);  // 推入右子树的左链
        return node.val;
    }
    public boolean hasNext() { return !stack.isEmpty(); }

    private void pushLeft(TreeNode node) {
        while (node != null) { stack.push(node); node = node.left; }
    }
}

恢复二叉搜索树（LeetCode 99）

有且只有两个节点被错误交换，找到它们并修复（O(n) 时间，O(1) 空间用 Morris 遍历）：

public void recoverTree(TreeNode root) {
    TreeNode first = null, second = null, prev = null;
    TreeNode cur = root, pred;
    // Morris 中序遍历
    while (cur != null) {
        if (cur.left == null) {
            // 访问 cur
            if (prev != null && prev.val > cur.val) {
                if (first == null) first = prev;
                second = cur;
            }
            prev = cur;
            cur = cur.right;
        } else {
            pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur; cur = cur.left;
            } else {
                pred.right = null;
                // 访问 cur
                if (prev != null && prev.val > cur.val) {
                    if (first == null) first = prev;
                    second = cur;
                }
                prev = cur;
                cur = cur.right;
            }
        }
    }
    // 交换
    int tmp = first.val; first.val = second.val; second.val = tmp;
}

BST 中第 K 小的元素（LeetCode 230）

中序遍历（递增序），第 k 次访问即为答案：

private int count = 0, result = 0;
public int kthSmallest(TreeNode root, int k) {
    inorder(root, k); return result;
}
private void inorder(TreeNode node, int k) {
    if (node == null) return;
    inorder(node.left, k);
    if (++count == k) { result = node.val; return; }
    inorder(node.right, k);
}

总结