98. 验证二叉搜索树
一句话套路上下界区间收缩(只比父子会错)
题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
思路
时间
O(n)空间
O(h)思路
自顶向下传递开区间 (lo, hi)。走左分支收紧上界为父值,走右分支收紧下界。
致命错误
只比较「结点与左右孩子」—— 那只能保证局部有序。
真正的反例是 [10,5,15,nullopt,nullopt,6,20]:每个结点都比左孩子大、比右孩子小,但 6 落在 10 的右子树里,就必须 > 10 —— 只有「自上而下传区间」能拒掉它。
(官方给的另一例 [5,1,4,nullopt,nullopt,3,6] 反而简单 —— 4 是 5 的右孩子却比 5 小,「只比父子」一眼就能拒掉,所以它并不能暴露这个 bug)用 long long 是因为边界要能表示 INT_MIN-1 / INT_MAX+1。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0098 {
class Solution {
public:
bool isValidBST(TreeNode* root) { return valid(root, LLONG_MIN, LLONG_MAX); }
private:
static bool valid(TreeNode* n, long long lo, long long hi) {
if (!n) return true;
if (n->val <= lo || n->val >= hi) return false; // 严格小于/大于
return valid(n->left, lo, n->val) && valid(n->right, n->val, hi);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0098::Solution s;
TreeNode* a = buildTree({2, 1, 3});
CHECK_TRUE(s.isValidBST(a));
freeTree(a);
TreeNode* b = buildTree({5, 1, 4, nullopt, nullopt, 3, 6}); // 4 是 5 的右孩子却比 5 小
CHECK_FALSE(s.isValidBST(b));
freeTree(b);
TreeNode* c = buildTree({1, nullopt, 1}); // 相等也不允许
CHECK_FALSE(s.isValidBST(c));
freeTree(c);
// 局部都合法、全局不合法:只比较父子结点的写法会在这一条上返回 true
TreeNode* d = buildTree({10, 5, 15, nullopt, nullopt, 6, 20});
CHECK_FALSE(s.isValidBST(d));
freeTree(d);
TreeNode* e = buildTree({INT_MIN});
CHECK_TRUE(s.isValidBST(e)); // 极值:用 int 边界会挂
freeTree(e);
lc0108::Solution s;
vector<int> a{-10, -3, 0, 5, 9};
TreeNode* t = s.sortedArrayToBST(a);
CHECK_EQ(lc0094::Solution::inorderTraversal(t), a); // 中序 == 有序数组
lc0098::Solution v; // 借用 Q98 交叉验证
CHECK_TRUE(v.isValidBST(t));
lc0104::Solution d;
CHECK_EQ(d.maxDepth(t), 3); // 5 个结点的平衡树高度 3
freeTree(t);