二叉树题解——验证二叉搜索树【LeetCode】后序遍历

98. 验证二叉搜索树

一、算法逻辑（逐步通顺讲解每一步思路）

这段算法使用了一种递归的思路：
每个节点返回它所在子树的 最小值和最大值，并在返回的过程中检查 BST 的合法性。

✅ 1️⃣ 定义递归函数 dfs(node)，其含义是：
对于以 node 为根的子树，返回其值域范围 (最小值, 最大值)。

✅ 2️⃣ 处理空节点（递归边界）：
当 node is None 时，说明是空子树，返回 (inf, -inf)：

空树最大值是 -inf，最小值是 +inf，便于后续比较中不干扰当前节点的合法判断。

✅ 3️⃣ 分别递归左右子树：

获取当前节点左右子树的最大/最小值。

✅ 4️⃣ 当前节点合法性判断（BST 核心条件）：

当前节点的值 x = node.val，必须满足：

即：当前节点必须大于左子树的最大值，小于右子树的最小值。

如果不满足，则立即返回非法标记 (−inf, +inf)，用来“污染”父节点的判断。

✅ 5️⃣ 当前子树的值域汇总：
如果合法，则当前子树的最小值为 min(l_min, x)，最大值为 max(r_max, x)，向上传递。

✅ 6️⃣ 最终检查：
顶层返回的是根节点子树的值域，如果合法，就不等于 (-inf, +inf)；否则被污染为非法。

二、核心点总结

该算法的核心是：

后序遍历地收集每棵子树的最值信息，同时判断当前节点是否满足 BST 性质。

✅ 通过最小/最大值来传递合法性，思路独特；
✅ 利用 (−inf, +inf) 作为非法标志，避免使用全局变量；
✅ 后序遍历先处理左右子树，再判断当前节点，能做到“非法剪枝”；
✅ 可扩展性强：该模式也可以改写为同时处理 AVL 树、红黑树的平衡性检测等。

class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def dfs(node: Optional[TreeNode]) -> Tuple:if node is None:return inf, -infl_min, l_max = dfs(node.left)r_min, r_max = dfs(node.right)x = node.val# 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了if x <= l_max or x >= r_min:return -inf, infreturn min(l_min, x), max(r_max, x)return dfs(root)[1] != inf