Vault 101

xjay2007's Blog

0%

LeetCode 98. 验证二叉搜索树

发表于 更新于 分类于 ， Valine：

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

题目第一反应，应该是遍历所有节点，判断 node->right->val > node->val 和 node->left->val < node->val 。不过这样与二叉搜索树的定义不符，应该是左子树所有节点的值都小于根节点的值，右子树同理。

中序遍历

思路

  • 由于二叉搜索树特性，中序遍历访问的元素是由小到大排列的顺序。
  • 使用栈来存储访问的元素。

复杂度分析

  • 时间复杂度：O(N) ，需要遍历所有节点。
  • 空间复杂度：O(N) 。

代码

  • 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// C++
bool isValidBST(TreeNode* root) {
    if (!root) {
        return true;
    }
    stack<TreeNode*> s;
    auto p = root;
    TreeNode* pre = NULL;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->left;
        }
        p = s.top();
        s.pop();
        // 中序遍历中，此节点值比上个节点值小
        if (pre && p->val <= pre->val) {
            return false;
        }
        pre = p;
        p = p->right;
    }
    return true;
}
  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++
TreeNode* pre;
bool dfs(TreeNode* root) {
    if (!root) {
        return true;
    }
    if (!dfs(root->left)) {
        return false;
    }
    if (pre && pre->val >= root->val) {
        return false;
    }
    pre = root;
    if (!dfs(root->right)) {
        return false;
    }
    return true;
}
bool isValidBST(TreeNode* root) {
    pre = NULL;
    return dfs(root);
}
相似文章