LeetCode HOT100 - 验证二叉搜索树

依然递归

子节点传上来是否合法，如果子树不合法那这棵树一定也不合法

然后我们进行二叉搜索树的性质判定

左子树为例，要判断都小于根节点，那么就只要把左子树的最大值拿出来比较就可以

右子树也是一样的

因此我们回传的时候传递是否合法，还有当前最大值和最小值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/using i64 = long long;
class Solution {
public:bool isValidBST(TreeNode* root) {auto dfs = [&](this auto&& self, TreeNode* x) -> array<i64, 3> {if (!x) {return {1, LLONG_MAX, LLONG_MIN};}auto l = self(x->left);auto r = self(x->right);if (!l[0] || !r[0]) {return {0, 0, 0};}if (l[2] >= x->val || r[1] <= x->val) {return {0, 0, 0};}array<i64, 3> res = {1, min<i64>({l[1], r[1], x->val}), max<i64>({l[2], r[2], x->val})};return res;};return dfs(root)[0];}
};

这里是自底向上的写法

实际上对于这题自顶向下也是可以的

也就是传递有效区间

// 当前节点超出上下界，直接剪枝
if (x->val <= lower || x->val >= upper) return false;
// 左子树的上限更新为当前节点的值，右子树的下限更新为当前节点的值
return self(x->left, lower, x->val) && self(x->right, x->val, upper);