老师,判断是否为二分搜索树 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回答

liuyubobobo

2018-12-13

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


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

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


1
1
Fengtony
谢谢老师!明白了
2018-12-13
共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程