验证二叉搜索树

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

解法一（中序遍历）：

/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long long prev = LLONG_MIN;
        return inorder(root, prev);
    }

private:
    bool inorder(TreeNode* node, long long& prev) {
        if (node == nullptr)
        {
            return true;
        }

        if (!inorder(node->left, prev))
        {
            return false;
        }

        if (node->val <= prev)
        {
            return false;
        }

        prev = node->val;

        return inorder(node->right, prev);
    }
};

解法二（递归上下界）：

/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, LLONG_MIN, LLONG_MAX);
    }

private:
    bool dfs(TreeNode* node, long long lower, long long upper) {
        if (node == nullptr)
        {
            return true;
        }

        if (node->val <= lower || node->val >= upper)
        {
            return false;
        }

        return dfs(node->left, lower, node->val) && dfs(node->right, node->val, upper);
    }
};

核心思想

判断二叉搜索树时，不能只比较一个节点和它的左右孩子。

例如：

    5
   / \
  1   6
     / \
    3   7

节点 6 本身满足 3 < 6 < 7，但节点 3 位于根节点 5 的右子树中，它必须严格大于 5。

所以这棵树不是二叉搜索树。

这题最关键的观察是：

二叉搜索树的限制不是只来自父节点，而是来自所有祖先节点。

常见做法有两种：

• 中序遍历：有效二叉搜索树的中序遍历结果必须严格递增。
• 递归上下界：每个节点都必须落在祖先节点传下来的合法区间内。

解法一：中序遍历

二叉搜索树有一个重要性质：

中序遍历结果严格递增

中序遍历顺序是：

左子树 -> 当前节点 -> 右子树

对于二叉搜索树来说：

• 左子树所有节点值都小于当前节点。
• 右子树所有节点值都大于当前节点。

所以按照中序遍历访问时，节点值应该越来越大。

代码中使用 prev 保存上一个访问到的节点值。

如果当前值满足：

node->val <= prev

说明中序序列不是严格递增，直接返回 false。

这里必须使用严格大于，而不是大于等于。

因为题目要求二叉搜索树中不能出现等于当前节点的值，重复值也是不合法的。

为什么 prev 要用 long long

题目中节点值范围是：

-2^31 <= Node.val <= 2^31 - 1

如果直接把 prev 初始化为 INT_MIN，当树中第一个访问到的节点值也等于 INT_MIN 时，会误判为不满足严格递增。

所以代码使用：

LLONG_MIN

它比任何合法的 Node.val 都小，可以安全作为初始值。

解法二：递归上下界

对于每个节点，它都有一个合法取值范围：

(lower, upper)

当前节点值必须满足：

lower < node->val < upper

一开始根节点没有祖先限制，所以范围是：

(LLONG_MIN, LLONG_MAX)

当递归进入左子树时，左子树所有节点都必须小于当前节点。

所以左子树的范围变成：

(lower, node->val)

当递归进入右子树时，右子树所有节点都必须大于当前节点。

所以右子树的范围变成：

(node->val, upper)

只要某个节点不在自己的合法区间内，就说明它违反了某个祖先节点传下来的限制。

这种写法更直接地对应了二叉搜索树的定义，也是推荐解法。

为什么不能只比较左右孩子

只比较：

left->val < root->val < right->val

是不够的。

因为二叉搜索树要求的是：

• 左子树所有节点都小于根节点。
• 右子树所有节点都大于根节点。

不是只有左右孩子满足关系就可以。

示例：

root = [5,1,4,null,null,3,6]

节点 4 作为根节点 5 的右孩子，已经小于 5，所以这棵树不合法。

即使在节点 4 自己的子树里，3 < 4 < 6 成立，也不能改变它违反祖先限制这一点。

边界情况

如果当前节点为空，说明这是一棵空子树。

空子树不会违反二叉搜索树性质，所以返回 true。

如果节点值等于边界值，也是不合法的。

因为二叉搜索树要求严格小于或严格大于。

如果树中存在重复值，中序遍历会出现相邻两个值相等，递归上下界中也会触发边界不满足。

因此重复值会被正确判定为非法。

如果节点值为 INT_MIN 或 INT_MAX，使用 long long 边界可以避免初始边界和真实节点值冲突。

正确性证明

我们证明：两个解法都能正确判断一棵树是否是有效二叉搜索树。

结论 1：中序遍历解法不会把非法二叉搜索树判断为合法

如果一棵树不是有效二叉搜索树，那么一定存在某个节点违反了二叉搜索树的顺序要求。

对于二叉搜索树，中序遍历结果必须严格递增。

如果某个左子树节点不小于祖先节点，或者某个右子树节点不大于祖先节点，那么中序遍历中就会出现后访问的值不大于前一个值的情况。

算法会检查：

node->val <= prev

一旦出现这种情况，就返回 false。

所以中序遍历解法不会把非法二叉搜索树判断为合法。

结论 2：中序遍历解法不会把合法二叉搜索树判断为非法

如果一棵树是有效二叉搜索树，那么左子树所有节点都严格小于根节点，右子树所有节点都严格大于根节点，并且左右子树自身也是二叉搜索树。

因此按中序遍历访问时，左子树中的所有值先出现，并且都小于根节点；根节点之后，右子树中的所有值出现，并且都大于根节点。

左右子树内部也满足同样性质。

所以整个中序遍历序列严格递增。

算法只会在当前值不大于前一个值时返回 false。

合法二叉搜索树不会出现这种情况。

所以中序遍历解法不会把合法二叉搜索树判断为非法。

结论 3：递归上下界解法不会漏掉祖先限制

递归函数 dfs(node, lower, upper) 表示：

判断以 node 为根的子树中，所有节点是否都严格落在 (lower, upper) 内

对于当前节点，算法先检查：

lower < node->val < upper

如果不满足，立即返回 false。

进入左子树时，算法把上界更新为 node->val。

进入右子树时，算法把下界更新为 node->val。

这样，祖先节点对当前子树的限制会通过 lower 和 upper 一直向下传递。

所以递归上下界解法不会漏掉任何祖先限制。

结论 4：递归上下界解法的判断条件和二叉搜索树定义一致

如果一个节点位于某个祖先的左子树中，它的值必须严格小于这个祖先。

如果一个节点位于某个祖先的右子树中，它的值必须严格大于这个祖先。

lower 保存当前节点必须严格大于的最大下界。

upper 保存当前节点必须严格小于的最小上界。

只要每个节点都满足：

lower < node->val < upper

并且左右子树递归检查也都成立，就说明每个节点都满足所有祖先传下来的二叉搜索树限制。

因此整棵树是有效二叉搜索树。

得出结论

由结论 1 和结论 2 可知，中序遍历解法判断结果正确。

由结论 3 和结论 4 可知，递归上下界解法判断结果正确。

因此两个解法都能正确判断二叉树是否是有效二叉搜索树。

举例理解

以：

root = [5,1,4,null,null,3,6]

为例，这棵树可以理解为：

    5
   / \
  1   4
     / \
    3   6

用递归上下界看：

节点 4 在根节点 5 的右子树中，所以它必须严格大于 5。

但 4 < 5，因此整棵树不是有效二叉搜索树。

用中序遍历看，这棵树的中序结果是：

[1, 5, 3, 4, 6]

这个序列不是严格递增，因为 3 < 5。

所以同样返回 false。

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点最多被访问一次。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点最多被访问一次，并且每次只进行常数次比较。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈。