LeetCode 98中等二叉树 · BST
验证二叉搜索树 图解题解
光比父子三人组不够——深处的节点也可能悄悄越界。
验证二叉搜索树别只盯着父子大小——得给每个节点带一个「允许的取值区间」往下传：往左子树走，上界收紧成当前值；往右走，下界抬高成当前值。任何节点越界就判否。这样祖先的约束被一路「继承」到每个后代，深处藏着的不合法节点也逃不掉。
这道题到底在问什么
验证是否为二叉搜索树：对每个节点，左子树所有值 < 它 < 右子树所有值。
- 树
- 5 →(3,8)，3→(1,4)，8→(7,9)
- 输出
- true
最优解：一步一步想明白
- 3最容易踩的笨/错办法：对每个节点只比它和左右直接孩子。问题是 BST 要求是「子树里所有节点」都满足，一个深处的孩子可能比某个祖先还大，光看父子三人组根本发现不了，会把非法树判成合法。
- 4转折：把约束当参数一路往下传。根的范围是 (−∞, +∞)；走到左孩子时上界收紧为「父值」、走到右孩子时下界收紧为「父值」。每个节点的值必须严格落在自己继承来的
(low, high)内。这样祖先的约束就被「带」到了每个后代身上，不会再漏判深处的节点。 - 55 ∈ (−∞, +∞)根 5 不受任何约束，范围 (−∞, +∞)，通过。往左走时把上界改成 5、往右走时把下界改成 5，分别传给两个孩子。
- 63 ∈ (−∞, 5)左孩子 3 继承的范围是 (−∞, 5)：上界由父亲 5 收紧。
3 < 5✓。再往下：3 的左孩子拿 (−∞, 3)、右孩子拿 (3, 5)。 - 78 ∈ (5, +∞)右孩子 8 继承范围 (5, +∞)：下界由父亲 5 收紧。
8 > 5✓。8 的左孩子将拿 (5, 8)、右孩子拿 (8, +∞)。 - 81 ∈ (−∞, 3)3 的左孩子 1：范围 (−∞, 3)，
1 < 3✓。叶子，无需再往下。 - 94 ∈ (3, 5)全题最关键的一个节点：4 是 3 的右孩子，但它整体在 5 的左子树里，所以范围是 (3, 5)——下界 3 来自父亲、上界 5 来自祖父。
3 < 4 < 5✓。这正是「只比父亲」会漏掉的约束。 - 106 ∈ (3, 5) ?把这个位置换成 6 看看：只跟父亲 3 比，
6 > 3像是合法；可它落在 5 的左子树，必须< 5。6 ≥ 5，越界！错办法会放过它，带上下界的办法一眼抓住。 - 116 ∉ (3, 5) → False一旦某节点落在自己的 (low, high) 之外，立刻判定整棵树不是 BST，return False。回到正例：正因为原来的 4 严格落在 (3,5) 内，才得以继续；下面把右子树也验完。
- 12全部 ✓ → True回到正例的 8 这一支：左孩子 7 在 (5, 8) ✓、右孩子 9 在 (8, +∞) ✓。所有节点都落在各自范围内 → 是合法 BST, return True。
- 15「祖先施加的约束，沿递归一路带给后代」是树递归的一个重要范式。另一招更简洁：BST 的中序遍历必然严格递增，中序走一遍看是否一直变大即可——两种方法都很经典。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：只比 node 和直接父亲/孩子
✓ 对：传 (low, high) 累积约束往下
右子树深处的节点也必须大于某个祖先根，光跟父比会把非法树误判为合法(本题的 6 就是反例)
✗ 错：用 <= 允许相等
✓ 对：BST 要严格 low < val < high
严格 BST 不允许重复值，写成 ≤ 会把有相等值的树错判为合法
完整代码（Python / C++ / Java）
Python
class Solution:
def isValidBST(self, root):
def dfs(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
return dfs(root, float('-inf'), float('inf'))C++
class Solution {
bool dfs(TreeNode* node, long low, long high) {
if (!node) return true;
if (!(low < node->val && node->val < high)) return false;
return dfs(node->left, low, node->val) && dfs(node->right, node->val, high);
}
public:
bool isValidBST(TreeNode* root) { return dfs(root, LONG_MIN, LONG_MAX); }
};Java
class Solution {
boolean dfs(TreeNode node, long low, long high) {
if (node == null) return true;
if (!(low < node.val && node.val < high)) return false;
return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
}
public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); }
}套路模板 · 带上下界的树递归（背下来）
def dfs(node, low, high):
if not node: return True
if not (low < node.val < high): return False
return (dfs(node.left, low, node.val) # 收上界
and dfs(node.right, node.val, high)) # 收下界class Solution {
bool dfs(TreeNode* node, long low, long high) {
if (!node) return true;
if (!(low < node->val && node->val < high)) return false;
return dfs(node->left, low, node->val) && dfs(node->right, node->val, high);
}
public:
bool isValidBST(TreeNode* root) { return dfs(root, LONG_MIN, LONG_MAX); }
};class Solution {
boolean dfs(TreeNode node, long low, long high) {
if (node == null) return true;
if (!(low < node.val && node.val < high)) return false;
return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
}
public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); }
}复杂度
时间复杂度
O(n)
每个节点检查一次
空间复杂度
O(h)
递归栈深度等于树高 h
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 验证二叉搜索树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么光比较「左孩子 ＜ 父 ＜ 右孩子」不够？+
那只保证局部；BST 要求左子树「所有」节点都小于根。必须带着祖先传下来的 (low,high) 全局区间逐点检查。
上下界怎么随递归更新？+
往左走：上界 high 收紧成当前节点值(左子树都要更小)；往右走：下界 low 收紧成当前节点值。
还有别的解法吗？+
中序遍历 BST 应得严格升序；边中序边比较「是否大于前一个值」，一旦不升序就不是 BST。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。