京公网安备11010502063487号给定一棵二叉树，判断它是不是有效的二叉搜索树：任意结点的左子树里所有结点的值都严格小于它，右子树里所有结点的值都严格大于它，左右子树本身也都是二叉搜索树。这里最常见的错误是只检查结点与它的直接左右孩子的关系，但规则要求的是整个子树。正确的做法是递归时把"允许的范围"往下传：根结点的范围是 (负无穷, 正无穷)；进入左孩子时，上界收紧成父结点的值；进入右孩子时，下界收紧成父结点的值。本文用真实数据展示只比较直接孩子的写法会错在哪里，用 Java 展示用 int 的最大最小值代替无穷的陷阱，给出五种语言的实现，并把范围传递做成分步演示。这是本系列带二叉树面板的又一个演示。
完整题目见官方页面（链接在文末）。树在测试里用 LeetCode 的层序数组表示，null 表示空位。结点的值可以是任意 32 位整数（包括 -2147483648 和 2147483647）。基准解用完全不同的性质：中序遍历，合法的二叉搜索树的中序序列必须严格递增。一共 15 组用例，覆盖：官方两个示例、空树、单个结点、重复的值（[1, 1]、[2, 2, 2]）、违反更上层祖先限制的树（右子树里有比根小的数）、值为 32 位整数最小或最大值的树：
输入 [[2,1,3]] 输出 true 输入 [[5,1,4,null,null,3,6]] 输出 false 输入 [[]] 输出 true 输入 [[1]] 输出 true 输入 [[1,1]] 输出 false 输入 [[2,2,2]] 输出 false
如果只检查每个结点与它的左右孩子的大小关系，[5, 4, 6, null, null, 3, 7] 会被认为是合法的：5 的左孩子 4 < 5，右孩子 6 > 5；6 的左孩子 3 < 6，右孩子 7 > 6。但 3 在 5 的右子树里，却比 5 小，违反了规则。下面是这种写法与 solve 的真实结果：
# 只比较结点与它的直接左右孩子的写法 [5, 4, 6, None, None, 3, 7]: 只比较直接孩子 -> True solve -> False [10, 5, 15, None, None, 6, 20]: 只比较直接孩子 -> True solve -> False [2, 1, 3]: 只比较直接孩子 -> True solve -> True [3, 1, 5, 0, 2, 4, 6]: 只比较直接孩子 -> True solve -> True 随机 20000 棵树：该写法与正确答案不同的有 784 棵（3.9%） 用 int 的最小、最大值代替无穷（Java 真实运行）： 只有一个结点 2147483647：int 当无穷 -> false；long 当无穷 -> true 只有一个结点 -2147483648：int 当无穷 -> false；long 当无穷 -> true
前两个例子只比较直接孩子的写法给出 True，正确答案是 False（3 和 6 分别是违反祖先限制的结点）；后两个合法的树两种写法一致。在随机的 20000 棵树里，只比较直接孩子的写法出错的有 784 棵，占 3.9%（大部分随机生成的非法树在根附近的直接孩子上就已经违规，能被两种写法同时发现，所以只有深处的违规才造成差别，这是我对这个比例偏低的一个推测，没有单独验证）。
范围检查需要一个"无穷"作为初始的上下界。如果偷懒用 Integer.MIN_VALUE 和 Integer.MAX_VALUE，那么结点值恰好等于这两个极值时，严格比较（val <= lo 或 val >= hi）会误判为非法。下面是真实运行的 Java 程序，用只有一个结点的树对比：
只有一个结点 2147483647 时，用 int 极值当无穷得到 false（因为 val >= hi 成立），用 long 当无穷得到正确的 true；-2147483648 同理。所以 Java、C++ 的实现都用 long / long long 存范围（Go 用 64 位的 int，JavaScript 用 Infinity）。用例里专门放了四棵含有 32 位整数极值的树。
check(node, lo, hi)：空结点返回真；如果 node.val 不严格落在 (lo, hi) 内，返回假；否则递归检查左子树 (lo, node.val) 和右子树 (node.val, hi)，两者都为真才为真。入口是 check(root, 负无穷, 正无穷)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；测试程序把层序数组建成真正的结点对象再调用。
Python · 解法代码class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def is_valid_bst(root): def check(node, lo, hi): # 这棵子树里所有结点的值都必须严格落在开区间 (lo, hi) 内 if node is None: return True if not (lo < node.val < hi): return False return check(node.left, lo, node.val) and check(node.right, node.val, hi) # 左子树的上界收紧成当前值，右子树的下界收紧成当前值 return check(root, float("-inf"), float("inf"))
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,1,3]] → true [[5,1,4,null,null,3,6]] → false [[]] → true [[1]] → true [[1,1]] → false [[2,2,2]] → false
Java · 解法代码class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } } class Solution { public boolean isValidBST(TreeNode root) { return check(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean check(TreeNode node, long lo, long hi) { // 这棵子树里所有结点的值都必须严格落在开区间 (lo, hi) 内 if (node == null) return true; if (node.val <= lo || node.val >= hi) return false; // 用 long 当"无穷"：结点值可能正好是 int 的最小或最大值 return check(node.left, lo, node.val) && check(node.right, node.val, hi); // 左子树上界收紧成当前值，右子树下界收紧成当前值 } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,1,3]] → true [[5,1,4,null,null,3,6]] → false [[]] → true [[1]] → true [[1,1]] → false [[2,2,2]] → false
Go · 解法代码import "math" type TreeNode struct { Val int Left, Right *TreeNode } func isValidBST(root *TreeNode) bool { var check func(node *TreeNode, lo, hi int) bool // 这棵子树里所有结点的值都必须严格落在开区间 (lo, hi) 内 check = func(node *TreeNode, lo, hi int) bool { if node == nil { return true } if node.Val <= lo || node.Val >= hi { // Go 的 int 是 64 位，用 math.MinInt64 / MaxInt64 当"无穷" return false } return check(node.Left, lo, node.Val) && check(node.Right, node.Val, hi) // 左子树上界收紧成当前值，右子树下界收紧成当前值 } return check(root, math.MinInt64, math.MaxInt64) }
$ go build -o bin . && ./bin < cases.jsonl [[2,1,3]] → true [[5,1,4,null,null,3,6]] → false [[]] → true [[1]] → true [[1,1]] → false [[2,2,2]] → false
JavaScript · 解法代码class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function isValidBST(root) { const check = (node, lo, hi) => { // 这棵子树里所有结点的值都必须严格落在开区间 (lo, hi) 内 if (node === null) return true; if (node.val <= lo || node.val >= hi) return false; return check(node.left, lo, node.val) && check(node.right, node.val, hi); // 左子树上界收紧成当前值，右子树下界收紧成当前值 }; return check(root, -Infinity, Infinity); }
$ node run.js < cases.jsonl [[2,1,3]] → true [[5,1,4,null,null,3,6]] → false [[]] → true [[1]] → true [[1,1]] → false [[2,2,2]] → false
C++ · 解法代码#include <climits> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; class Solution { bool check(TreeNode* node, long long lo, long long hi) { // 这棵子树里所有结点的值都必须严格落在开区间 (lo, hi) 内 if (!node) return true; if (node->val <= lo || node->val >= hi) return false; // 用 long long 当"无穷"：结点值可能正好是 int 的最小或最大值 return check(node->left, lo, node->val) && check(node->right, node->val, hi); // 左子树上界收紧成当前值，右子树下界收紧成当前值 } public: bool isValidBST(TreeNode* root) { return check(root, LLONG_MIN, LLONG_MAX); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,1,3]] → true [[5,1,4,null,null,3,6]] → false [[]] → true [[1]] → true [[1,1]] → false [[2,2,2]] → false
共 15 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 15/15 Java 通过 15/15 Go 通过 15/15 JavaScript 通过 15/15 C++ 通过 15/15
Python 版本另外和中序遍历判断做了随机对拍：一半是随机生成的合法二叉搜索树（其中 60% 会被随机改写一个结点的值，可能变得非法），一半是随机形状、随机取值的二叉树：
随机对拍 30000 组（一半是随机生成的合法二叉搜索树（60% 的概率随机改写一个结点的值），一半是随机形状、随机取值的二叉树），solve 与 brute 的结果全部一致。
另外四种语言只在上面 15 组固定用例上验证过，没有做大规模随机对拍。这道题每个结点只访问一次，是线性的，所以没有做规模对比实验。
下面的演示用树 [5, 3, 8, 2, 4, 7, 9, null, null, null, 6]。根 5 的范围是 (-∞, +∞)；左孩子 3 的范围变成 (-∞, 5)；3 的左孩子 2 的范围是 (-∞, 3)，右孩子 4 的范围是 (3, 5)；4 的右孩子 6 的范围是 (4, 5)，但 6 不在这个范围内（它比祖先 5 大，却出现在 5 的左子树里），返回假。注意 6 与它的父结点 4 的关系是对的（6 > 4），只有把祖先给出的界限一起带下来才能发现。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。