HHot 100C++ 图解

98. 验证二叉搜索树

中等 二叉树 3 帧动画 在力扣上做

一句话套路上下界区间收缩(只比父子会错)

题目描述

给你一个二叉树的根节点 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。

图解

1 5 3 4 6
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp13 行
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);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q98_validate_bst17 行
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);
TEST q108_array_to_bst9 行
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);

↑↓ 选择↵ 打开/ 随时唤起