DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer minValue, Integer maxValue) {
if (node == null) {
return true;
}
if (minValue != null && node.val <= minValue) {
return false;
}
if (maxValue != null && node.val >= maxValue) {
return false;
}
return isValidBST(node.left, minValue, node.val) && isValidBST(node.right, node.val, maxValue);
}
}
|
需要注意的是题目要求节点的左子树中的所有节点值小于当前节点，右子树中的所有节点值大于当前节点，而不仅是左子节点小于当前节点，右子节点大于当前节点。
DFS
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
| class Solution {
private static class State {
private Integer preValue;
}
public boolean isValidBST(TreeNode root) {
State state = new State();
return dfs(root, state);
}
private boolean dfs(TreeNode node, State state) {
if (node == null) {
return true;
}
if (!dfs(node.left, state)) {
return false;
}
if (state.preValue != null && node.val <= state.preValue) {
return false;
}
state.preValue = node.val;
return dfs(node.right, state);
}
}
|
Iterate
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
| class Solution {
public boolean isValidBST(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
if (pre != null && node.val <= pre.val) {
return false;
}
pre = node;
root = node.right;
}
return true;
}
}
|
我们利用二叉搜索树的中序遍历为递增的特性，采用中序遍历来检查一个树是否是二叉搜索树。
References
98. Validate Binary Search Tree