Keshawn_lu's Blog

Leetcode 98. 验证二叉搜索树

字数统计: 332阅读时长: 1 min
2020/05/05 Share

题目简介

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

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

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

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

思路:因为是二叉搜索树,所以最左边的值最小,最右边的值最大,所以我们可以采用中序遍历,即先遍历左子树,再访问根节点,再遍历右子树。只有当前节点的值大于上一个遍历到的点的值,才符合搜索树的定义,不然直接返回false。

代码如下:

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
long pre = -10000000000; //记录上一个点的值
bool isValidBST(TreeNode* root) {

if(root == NULL)
return true;

if(!isValidBST(root->left))
return false;

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

if(!isValidBST(root->right))
return false;

return true;

}
};
CATALOG
  1. 1. 题目简介