TikTok 判断 BST：祖先范围与重复键合同

题目重点：用祖先上下界检查所有节点，说明局部比较不足，并避免数值哨兵。

题意与假设

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

训练无环二叉树，严格左<根<右，重复值非法；重复允许时需重新定义落在哪侧。

解题路线

只检查直接孩子无法约束孙子。例如根10、左5的右12，局部5<12却违反整棵左子树都<10。
DFS 带 low/high，左递归收紧 high=node.value，右收紧 low；每节点同时满足所有祖先形成的最紧边界。
用 None 表示无界，避免 INT_MIN/MAX 恰等真实值时误拒绝；迭代栈避免递归过深。
另一独立判法是中序序列严格递增，适合作验证参考；允许重复的规则可能无法仅凭非递减中序区分方向。

手动走一遍

10.left=5，5.right=12拒绝；合法单节点即便值极大也通过。空树合法；两个相等值在本合同下不合法。

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) DFS 栈空间，退化树 h=n；不改变原树。

易错点与追问

容易失分的边界

只比较孩子。
有限整数当无限边界。
重复策略未确认。

继续深挖

允许重复只在右侧怎样调整界？
输入可能有环如何处理？