老师，判断是否为二分搜索树 isBST() 这个方法，利用左孩子比根节点小，右孩子比根节点大这个性质不可以吗

Question

老师您好，我想问下判断是否为二分搜索树 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;
    }

Answer 1

liuyubobobo 2018-12-13 14:45:31

不够。左子树的所有节点必须都比根节点小；右子树的所有节点必须都比根节点大。

比如下面的二叉树不是BST.

     5
    / \
  3     8
 / \   / \
1   7 2   9

• 提问者 Fengtony #1

  谢谢老师！明白了