老师,判断是否为二分搜索树 isBST() 这个方法,利用左孩子比根节点小,右孩子比根节点大这个性质不可以吗
来源:12-3 检查二分搜索树性质和平衡性
Fengtony
2018-12-13
老师您好,我想问下判断是否为二分搜索树 isBST() 这个方法,利用左孩子比根节点小,右孩子比根节点大这个性质不可以吗?我尝试着写了下然后简单测试了好像也没有问题,还是有什么我没考虑到的吗?或者是存在隐藏的问题?
/**
* 是否为二分搜索树
*
* @return
*/
public boolean isBST() {
return isBST(root);
}
private boolean isBST(Node node) {
if ((node.left != null && node.left.key.compareTo(node.key) > 0)
|| (node.right != null && node.right.key.compareTo(node.key) < 0)) {
return false;
}
if (node.left != null) {
return isBST(node.left);
}
if (node.right != null) {
return isBST(node.right);
}
return true;
}
写回答
1回答
-
不够。左子树的所有节点必须都比根节点小;右子树的所有节点必须都比根节点大。
比如下面的二叉树不是BST.
5 / \ 3 8 / \ / \ 1 7 2 9
112018-12-13
相似问题