📝 题目描述

题目链接：验证二叉搜索树

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

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

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

子树：treeName 树中的一个节点及其所有子孙节点所构成的树称为 treeName 的 子树。

示例：

示例 1：

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

示例 2：

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

提示：

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

💡 解题思路

方法一：中序遍历

还记得“将有序数组转换为二叉搜索树”吗？在这里面我们提到：

二叉搜索树的中序遍历得到的值构成的序列一定是升序的。

据此，我们可以对题目中的二叉树进行中序遍历，检查得到的值是否是严格升序的。

这里要注意我们需使用 int64_t 进行比较，否则如果第一个节点就是 -2^31 我们无法进行判断。

方法二：递归

我们设计一个递归函数 judgeTree(tn, lower, upper) 来递归判断，函数表示考虑以 tn 为根的子树，判断子树中所有节点的值是否都在 (lower, upper) 的范围内（注意是开区间）。如果 tn 节点的值 val 不在 (lower, upper) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 tn -> val，即调用 judgeTree(tn -> left, lower, tn -> val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 tn -> val，即调用 judgeTree(tn -> right, tn -> val, upper)。

🔧 代码实现

1、中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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) {
        if (!root) return true;
        stack<TreeNode*> st;
        TreeNode* ptr = root;
        int64_t lastNum = INT64_MIN;
        while(!st.empty() || ptr != nullptr) {
            if (ptr != nullptr) {
                st.push(ptr);
                ptr = ptr -> left;
            } else {
                ptr = st.top();
                st.pop();
                if (lastNum >= ptr -> val) {
                    return false;
                }
                lastNum = ptr -> val;
                ptr = ptr -> right;
            }
        }
        return true;
    }
};

2、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 judgeTree(TreeNode* tn, int64_t lower, int64_t upper) {
        if (!tn) return true;
        if (tn -> val <= lower || tn -> val >= upper) {
            return false;
        }
        return judgeTree(tn -> left, lower, (int64_t) tn -> val) && judgeTree(tn -> right, (int64_t) tn -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return judgeTree(root, INT64_MIN, INT64_MAX);
    }
};

📊 复杂度分析

1、中序遍历

  • 时间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)O(n)。
  • 空间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n)O(n) 的空间。

2、递归

  • 时间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)O(n)。
  • 空间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n)O(n)。

🎯 总结

  • 核心思想：中序遍历 ⇋ 二叉搜索树 的思想。