LC98　验证二叉搜索树¶

中等通过率 41.3%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索二叉搜索树二叉树

一句话

自顶向下带着 (下界, 上界) 走，每个节点只跟自己的区间比。

解题思路¶

这题考什么¶

BST（二叉搜索树）的定义约束的是整棵子树：左子树里的所有节点严格小于当前节点，右子树里的所有节点严格大于当前节点。最常见的错解是只看父子三点 left.val < node.val < right.val —— 这个条件对每个节点单独成立，树却未必是 BST：

题面示例 2 的 [5,1,4,null,null,3,6]
         5
        / |
       1   4
          / |
         3   6
看父子：1 < 5 合法，3 < 4 < 6 也合法；
但 3 在 5 的右子树里却比 5 小，不是 BST。

正确的刻画是给每个节点配一个开区间 (low, high)，表示「这棵子树里的所有值必须落在其中」。根的区间两侧都无约束；往左走时上界收紧成父节点的值，往右走时下界收紧成父节点的值。区间是从根一路传下来的，因此自动包含了所有祖先的约束 —— 上例中走到 3 时区间是 (5, 4)，一比就出局。

等价的另一条路是「BST 的中序遍历严格递增」，牛客同题 BM34 用的就是它。上下界版的好处是每个节点的判据自足，不依赖前一个访问到的节点。

这里用显式栈做深度优先搜索（DFS），栈元素是三元组 (节点, 下界, 上界)。

数据规模与复杂度¶

节点数在 [1, 10^4]，节点值满足 -2^31 <= val <= 2^31 - 1。每个节点入栈出栈各一次、比较两次，时间 O(n)；空间 O(h)，h 为树高。链状树的 h 就是 1e4，远超 CPython 默认的 1000 层递归上限，所以 DFS 必须写成显式栈，递归版会 RecursionError；递归改迭代的三种改法见 DFS 深度优先搜索的 60.4 节。

坑在哪¶

区间要一路传下去，不能只跟父节点比。示例 2 就是为打掉「只比父子」准备的：3 的父亲是 4，父子关系挑不出毛病，是祖先 5 的约束把它判死。
哨兵不能取具体数字。值域下界正好是 -2^31、上界正好是 2^31 - 1，拿这两个数当初始边界，遇到根值恰好等于边界的树就会在第一次比较时误判。这里用 None 表示「这一侧还没有约束」，完全不依赖值域； float("-inf") 与 float("inf") 也可用，但 None 读起来更直白。
必须严格不等。题面写的是「严格小于」「严格大于」，等号不允许，所以判否条件是 val <= low 或 val >= high。写成 < 与 > 会把 [2,2] 这种含相等值的树误判成合法 BST。
发现越界立刻返回 False。这是合法的提前退出：BST 要求所有节点同时满足，一个节点出局整棵树就废了，没有必要遍历完。
空节点照压不误，弹出后统一跳过。若在压栈处逐个判空，左右两条分支各要写一遍，反而更容易漏掉一处。

参考实现¶

solutions/leetcode/LC98/sol.py
from typing import List, Optional


class Solution:
    def isValidBST(self, root: "Optional[TreeNode]") -> bool:
        # 栈元素是 (节点, 下界, 上界)；界取 None 表示「这一侧还没有任何约束」，
        # 用 None 而不是 -2^31 是因为节点值本身就能取到值域的两个端点
        stack = [(root, None, None)]
        # 循环不变量：栈里每棵子树的合法值域已经折叠进它自己的两个界，
        # 全部祖先的约束都在里面，不必再回头看父节点
        while stack:
            node, low, high = stack.pop()
            # 空子树天然合法；判空放在弹出后，压栈处就不用重复写两遍
            if node is None:
                continue
            # 严格不等：题面要求左子树「严格小于」、右子树「严格大于」，等号不允许
            if low is not None and node.val <= low:
                return False
            if high is not None and node.val >= high:
                return False
            # 往左走上界收紧成当前值、下界继承；往右走下界收紧成当前值、上界继承
            stack.append((node.left, low, node.val))
            stack.append((node.right, node.val, high))
        # 所有节点都落在各自的区间里，整棵树是 BST
        return True

LC98 验证二叉搜索树¶