Leetcode98. 验证二叉搜索树

题目描述

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

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

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

示例 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 。

解题思路

要想解答这道题，我们先回忆一下二叉搜索树的特性。

二叉搜索树的特性：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树
  • 二叉搜索树按中序遍历得到的序列是从小到大排列的

根据二叉树的特性我们可以写出判断是否为二叉搜索树的算法。我们可以用前三条特性得出算法一，它的难点在于如何判断一个节点的左子树的所有节点都小于当前节点以及这个节点的右子树的所有节点都大于当前节点；我们可以根据第四条特性得到算法二，它的难点在于在中序遍历的过程中怎么和上一个元素进行比较。

算法一：简单粗暴递归法

为了判断一个节点的左子树的所有节点是否都小于当前节点以及这个节点的右子树的所有节点是否都大于当前节点，我们设计一个递归函数isBST(TreeNode* root,long long left,long long right)来判断以root为根的子树，判断子树中的所有结点的值是否都在(left,right)区间内。如果不满足，说明不是一棵二叉搜索树，返回false。

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

left和right的初始值分别设为负无穷大和正无穷大。注意应该用long long类型来避免溢出。

算法二：中序遍历法

这个方法属于对中序遍历的修改。主要在于需要对当前结点的上一个结点pre需要先定义后修改。详见代码。

示例代码

算法一：简单粗暴递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) {}
};

bool isBST(TreeNode* root,long long left,long long right)
{
    if(!root) return true;
    if(root->val>=right || root->val<=left)
    {
        return false;
    }
    return isBST(root->left,left,root->val)&&isBST(root->right,root->val,right);
}

bool isValidBST(TreeNode* root)
{
    return isBST(root,LONG_MIN,LONG_MAX);
}

时间复杂度为：O(n)O(n)，nn为二叉树的结点个数

空间复杂度为：O(n)O(n)，nn为二叉树的结点个数

算法二：中序遍历法

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
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) {}
};

bool isBST1(TreeNode* root)
{
    if(!root) return true;
    bool left=isBST1(root->left);
    if(root->val<=pre)
    {
        return false;
    }
    pre=root->val;
    bool right=isBST1(root->right);
    return left&&right;
}

bool isValidBST(TreeNode* root)
{
    return isBST1(root);
}

时间复杂度为：O(n)O(n)，nn为二叉树的结点个数

空间复杂度为：O(n)O(n)，nn为二叉树的结点个数