题目简介
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 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
|
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;
}
};
|
