Amazon LC98：验证 BST 为什么必须传全局上下界？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入有限无环二叉树，整数键，所有左后代严格小于本节点、右后代严格大于；重复不合法。
• 空树合法。若应用允许重复，必须说明只放哪侧与区间开闭，不把标准政策静默改掉。

解题路线

1. 节点收到祖先约束(low,high)，校验low<value<high；向左缩上界为当前值，向右提高下界。祖先界持续传下去。
2. 区间不变量保证节点同时满足所有祖先路径约束：左子树不仅小于直接父，还要满足更早右转/左转造成的界。局部只比较父子漏掉跨祖先违规。
3. 用显式栈存(node,low,high)，None代表无界，避免32位/64位极值哨兵误伤合法大整数，也避免深树递归限制。
4. 另一个独立判据是中序序列严格递增；可以迭代维护previous减少存储，无需完整遍历数组。文章代码用上下界，验证器用中序，避免同算法自证。

手动走一遍

根5、右10、10左4：4<10看似局部正确，却违反根5的右子树下界。区间法在4收到(5,10)直接拒绝。10,000随机树与中序严格递增独立对照，10,000节点深链也通过。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from dataclasses import dataclass


@dataclass(eq=False)
class Node:
    value: int
    left: "Node | None" = None
    right: "Node | None" = None


def is_valid_bst(root):
    """Strict ordering, no duplicate keys; assumes an acyclic binary tree."""
    stack = [(root, None, None)]
    while stack:
        node, low, high = stack.pop()
        if node is None:
            continue
        if low is not None and node.value <= low:
            return False
        if high is not None and node.value >= high:
            return False
        stack.append((node.right, node.value, high))
        stack.append((node.left, low, node.value))
    return True

复杂度

O(n)时间、O(h)栈；平衡h=O(log n)，退化h=O(n)，不能一概说log空间。每节点访问一次，整数比较成本随位宽变化。

易错点与追问

容易失分的边界

• 只比较直接孩子。
• 把等号放宽允许重复。
• 用最小整数当负无穷。
• 深树递归栈溢出。

继续深挖

• 允许重复仅右侧怎么改区间？
• 输入可能有共享节点/环怎样检查？
• 只给前序遍历能否判断存在合法BST？