leetcode98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
开始想了很多笨方法，后来想起来中序遍历就是一个升序数组，可以根据这个判断。
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
dfs(root);
for (int i = 1 ;i < list.size(); i++) {
if (list.get(i) <= list.get(i - 1)) {
return false;
}
}
return true;
}
public boolean flag = true;
List<Integer> list = new ArrayList<>(20);
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
list.add(root.val);
dfs(root.right);
}
}
|
其实也可以不用数组存储，因为最后我们只跟前一个去比较，直接用一个prev记录前一个就行。
注意测试样例有 [-2147483648] 。所以最小值要用long类型的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
dfs(root);
return flag;
}
public boolean flag = true;
long prev = Long.MIN_VALUE;
List<Integer> list = new ArrayList<>(20);
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (root.val <= prev) {
flag = false;
return;
}
prev = root.val;
dfs(root.right);
}
}
|
leetcode 93/100