vvrf / DSA.log

问题拆解

判断一棵二叉树是不是二叉搜索树：左子树所有节点都小于根，右子树所有节点都大于根，且左右子树自身也是 BST。

最经典的错误写法是只检查每个节点和它的直接孩子：left.val < node.val < right.val。这个条件太弱了。反例：根为 5，左孩子 3，左孩子的右孩子是 6——每对父子都满足大小关系，但 6 出现在了根的左子树里，比根还大，整棵树不是 BST。

问题出在“小于根”是对整棵左子树的要求，不是只对左孩子。换句话说，每个节点的合法取值范围由它的所有祖先共同决定：往左走一步，上界收紧为父节点的值；往右走一步，下界收紧。只要递归时把这对界传下去，约束就从“局部”变成了“全局”。

BST 的定义写的是“左子树所有节点”，而不是“左孩子”。把祖先的约束浓缩成一对 (low, high) 开区间传下去，是让全局约束可递归的关键。

上下界递归

界的初值是“无穷”。用 Long.MIN_VALUE 之类的哨兵会在节点值恰好取到整型边界时误判，更稳妥的做法是用可空类型表示“无界”。

public boolean isValidBST(TreeNode root) {
    return valid(root, null, null); // null 表示无界
}

private boolean valid(TreeNode node, Integer low, Integer high) {
    if (node == null) {
        return true;
    }
    // 开区间：必须严格落在 (low, high) 内
    if (low != null && node.val <= low) {
        return false;
    }
    if (high != null && node.val >= high) {
        return false;
    }
    return valid(node.left, low, node.val)
        && valid(node.right, node.val, high);
}

def isValidBST(root: Optional[TreeNode]) -> bool:
    def valid(node, low, high):  # None 表示无界
        if node is None:
            return True
        # 开区间：必须严格落在 (low, high) 内
        if low is not None and node.val <= low:
            return False
        if high is not None and node.val >= high:
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, None, None)

func isValidBST(root *TreeNode) bool {
    var valid func(node *TreeNode, low, high *int) bool // nil 表示无界
    valid = func(node *TreeNode, low, high *int) bool {
        if node == nil {
            return true
        }
        // 开区间：必须严格落在 (low, high) 内
        if low != nil && node.Val <= *low {
            return false
        }
        if high != nil && node.Val >= *high {
            return false
        }
        return valid(node.Left, low, &node.Val) && valid(node.Right, &node.Val, high)
    }
    return valid(root, nil, nil)
}

pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    // None 表示无界
    fn valid(node: &Option<Rc<RefCell<TreeNode>>>, low: Option<i32>, high: Option<i32>) -> bool {
        match node {
            None => true,
            Some(rc) => {
                let n = rc.borrow();
                // 开区间：必须严格落在 (low, high) 内
                if low.is_some_and(|l| n.val <= l) || high.is_some_and(|h| n.val >= h) {
                    return false;
                }
                valid(&n.left, low, Some(n.val)) && valid(&n.right, Some(n.val), high)
            }
        }
    }
    valid(&root, None, None)
}

两处细节值得盯一眼。第一，比较必须带等号：BST 不允许相等值，node.val <= low 就要判假——用例里专门有 [2,2,2] 这种树。第二，往左递归时只收紧上界、下界原样传递，往右相反；写反一处，整棵树的判断就会静默出错。

另一条思路是中序遍历：BST 的中序序列严格递增，遍历时记住前驱、发现不增即返回假。两种写法复杂度相同，上下界版更直接地对应定义，中序版则在“找 BST 中第 k 小”这类题里更常用。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点检查一次
空间	`O(h)`	递归栈深度为树高，最坏退化成 O(n)

可以迁移的模式

递归验证全局性质时，把祖先施加的约束整理成参数（这里是一对上下界）随递归下传；
“无穷”哨兵值有整型边界风险，可空类型（null / None / Option）是更干净的表达；
中序遍历严格递增是 BST 的等价刻画，很多 BST 题都从这条性质切入。

看到“验证某种递归定义的结构”，先问一句：约束是局部的还是全局的？只查父子这类局部检查，往往正是出题人埋的坑。