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

有效 二叉搜索树定义如下：

节点的左子树只包含 严格小于 当前节点的数。

节点的右子树只包含 严格大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

**输入：**root = [2,1,3]
**输出：**true

示例 2：

**输入：**root = [5,1,4,null,null,3,6]
**输出：**false
**解释：**根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10(4)] 内

-2(31) <= Node.val <= 2(31) - 1

对于二叉搜索树每个节点都有严格的上下界

所以可以通过递归对每个结点进行判断，传入上下界即可

左节点上界为根，下界与根的下界相同

右节点上界与根的上界相同，下界为根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return BSThelper(root, LONG_MAX, LONG_MIN);
    }
    bool BSThelper(TreeNode *root, long long maxV, long long minV) {
        if (root == nullptr)
            return true;
        if (root->val >= maxV || root->val <= minV)
            return false;
        return BSThelper(root->left, root->val, minV) &&
               BSThelper(root->right, maxV, root->val);
    }
};

由于二叉搜索树的中序遍历是从小到大排列的

所以我们可以直接进行中序遍历，检查当前元素的值是否大于前一个已经遍历的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (root == nullptr)
            return false;
        long long last = LONG_MIN;
        stack<TreeNode *> s;
        TreeNode *cur = root;
        while (!s.empty() || cur != nullptr) {
            while (cur != nullptr) {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            if (cur->val <= last)
                return false;

            last = cur->val;
            cur = cur->right;
        }
        return true;
    }
};

递归中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        long long last = LONG_MIN;
        return helper(root, last);
    }

    bool helper(TreeNode *root, long long &last) {
        if (root == nullptr)
            return true;

        if (!helper(root->left, last))
            return false;

        if (root->val <= last)
            return false;
        last = root->val;

        return helper(root->right, last);
    }
};