04.05. 合法二叉搜索树
难度 中等
实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 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 。
|
题解
1. 递归
由于是二叉搜索树，因此其左右子树也均为二叉搜索树，我们对其递归遍历所有子树是否为二叉搜索树即可。但要注意的是子树的取值是有上限与下限的，对于root右子树的左子树，所有的值需要大于root.val但又需要小于root.right.val
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isValidBST(TreeNode root) {
return is(root,null,null);
}
public boolean is(TreeNode node,Integer low,Integer top){
if(node == null)
return true;
int val = node.val;
if (low != null && val <= low) {
return false;
}
if (top != null && val >= top) {
return false;
}
return is(node.left,low,val)&&is(node.right,val,top);
}
}
|
空间复杂度：O(n) n为二叉树节点个数
时间复杂度：O(n) n为二叉树节点个数
2. 中序遍历
我们也可以使用中序遍历的方式对二叉搜索树进行遍历，我们只需比较当前节点的值与中序遍历的前一个节点的值即可。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
Integer pre = null;
while(!stack.isEmpty()||root!=null){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre!=null&&root.val<=pre)
return false;
pre = root.val;
root = root.right;
}
return true;
}
}
|
空间复杂度：O(n) n为二叉树节点个数
时间复杂度：O(n) n为二叉树节点个数