LeetCode 刷题 [C++] 第98题.验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。
  

题目分析

由题目可知，二叉搜索树的特征：二叉搜索树的左子树上所有节点的值均小于根节点；右子树上所有节点的值均大于根节点的值；它的左右子树也是二叉搜索树。
因此，我们可以使用递归思想来解决这个问题：

1. 递归结束条件为当前访问节点为空时，返回true；
2. 检查当前节点的左子树，若返回false，则直接返回，结束查询；
3. 检查当前节点的值是否合法，不合法返回false；
4. 检查当前节点的右子树，并返回其和左子树的与值。

Code

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
private:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (nullptr == root) {
            return true;
        }
        bool lf = helper(root->left, lower, root->val);
        if (!lf) {
            return false;
        }
        if (root->val <= lower || root->val >= upper) {
            return false;
        }
        return lf && helper(root->right, root->val, upper);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20