验证二叉搜索树 图解题解

BST 的定义比看起来更严格

二叉搜索树（BST）的约束是：每个节点的「左子树里所有值」都小于它、「右子树里所有值」都大于它——注意是整棵子树，不只是直接的左右孩子。这个「所有」正是本题的陷阱所在：一个值可能和它的父亲比完全正常，却违反了更上层祖先立下的范围约束。判断合法性必须能管住这种跨层的违规。

为什么只比较父子三个节点会漏判

最直觉的做法是对每个节点检查「左孩子 < 我 < 右孩子」。它只保证了局部有序，管不到跨层：比如根是 5、右孩子是 6，而 6 的左孩子是 3——这三个点里 3 < 6 没毛病，但 3 落在根 5 的右子树里，按定义右子树所有值必须大于 5，整棵树其实不合法。逐点的局部检查发现不了，因为约束是祖先传下来的「取值区间」，不是相邻两代的大小关系。

为什么中序遍历能一锤定音

关键观察：把 BST 按「左、根、右」的中序顺序展开，得到的值序列一定是严格递增的。道理可以递归地想——左子树的值全体小于根、又都排在根前面，右子树的值全体大于根、又都排在根后面，两棵子树内部再套用同样的论证。反过来，只要中序序列在某处不增，就说明某个「小于/大于整棵子树」的约束被打破了。于是复杂的树形区间约束被压平成一句话：中序序列是否严格递增。

实现上不用真把序列存出来：中序遍历（递归或用栈迭代）过程中维护一个变量 prev 记住上一个访问的值，每访问一个节点就和 prev 比一次，node.val <= prev 即刻返回 false，全程通过则返回 true。空间从存整个序列的 O(n) 省到 O(h)。

为什么相等也要判不合法

BST 定义要求严格大于、严格小于，值相等同样违规，所以比较必须写 node.val <= prev 而不是 <。这也解释了 prev 的初值为什么用 None（空值）而不是某个「足够小的数」：节点值可能取到整型的最小值，用具体数字兜底就可能在极值输入上误判；先判 prev is not None 再比较，第一个节点天然免比。

另一条路：带上下界的递归

等价的写法是把祖先的约束显式传下去：isValid(node, lo, hi) 要求 lo < node.val < hi，往左走把上界收紧为自己（hi = node.val），往右走把下界收紧为自己（lo = node.val）。这就是把「整棵子树的取值区间」写成了参数，正面解决跨层问题。两种写法都是 O(n) 时间、O(h) 空间；中序版更直观，上下界版则不需要 prev 变量，面试里任选其一都站得住。

复杂度与边界提醒

时间 O(n)：每个节点被中序访问恰好一次，比较是常数时间。空间 O(h)：显式栈或递归栈的深度等于树高，最坏（链状树）O(n)。

边界上除了前面说的相等值和极值初值，还要记得空树按约定是合法 BST，循环体一次都不进、直接返回 true 即可。

Python

def isValidBST(root):
    prev = None                  # 上一个中序访问到的值
    stack, node = [], root
    while stack or node:
        while node:              # 一路向左压栈
            stack.append(node); node = node.left
        node = stack.pop()       # 中序访问
        if prev is not None and node.val <= prev:
            return False         # 出现非递增 → 不是 BST
        prev = node.val
        node = node.right
    return True

Java

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    Integer prev = null;          // 上一个中序值
    while (!stack.isEmpty() || node != null) {
        while (node != null) {     // 一路向左
            stack.push(node); node = node.left;
        }
        node = stack.pop();        // 中序访问
        if (prev != null && node.val <= prev) return false;
        prev = node.val;
        node = node.right;
    }
    return true;
}

C++

bool isValidBST(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    long prev = LONG_MIN;          // 上一个中序值
    bool started = false;
    while (!st.empty() || node) {
        while (node) { st.push(node); node = node->left; }
        node = st.top(); st.pop();  // 中序访问
        if (started && node->val <= prev) return false;
        prev = node->val; started = true;
        node = node->right;
    }
    return true;
}