Validate BST: Implement a function to check if a binary tree is a binary search tree.
Hints: #35, #57, #86, #113, #128
解法1 （审题错误）
二叉查找树的规则是，node.left <= node < node.right ，注意对于相等的元素必须选一边放，这里选的是左边。
用递归的方式判断：
1
2
3
4
5
6
7
8
9
10
11
12
|
public boolean validateBST(Node node) {
if (node == null) {
return true;
}
if (node.left != null && node.left.value > node.value) {
return false;
}
if (node.right != null && node.value >= node.right.value) {
return false;
}
return validateBST(node.value) && validateBST(node.value);
}
|
解法2
解法1会认为下面这种情况是OK的：
1
2
3
4
5
|
5
/ \
2 8
/ \
1 9
|
其实准确的BST的定义是，all left nodes <= node < all right nodes。
如果是一个BST，那么这个树的每个节点的取值范围根据层数的递增而逐渐收敛的。看下面：
1
2
3
4
5
|
5 (null, null)
/ \
3 7 (null, 5), (5, null)
/ \ / \
2 4 6 8 (null, 3), (3, 5), (5, 7), (7, null)
|
所以这样解（这里为了简便采取的假设没有重复元素，all left nodes < node < all right nodes ）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public boolean validateBST(Node node, Integer min, Integer max) {
if (node == null) {
return true;
}
if (min != null && !(min < node.value)) {
return false;
}
if (max != null && !(node.value < max)) {
return false;
}
return validateBST(node.left, min, node.value)
&& valdateBST(node.right, node.value, max);
}
validateBST(root, null, null);
|
评论