首页 > 代码库 > 判断一棵树是否为二叉排序树

判断一棵树是否为二叉排序树

今天看到了一段判断是否为二叉排序树的代码,感觉有点问题,在网上一搜还真有不少这么做的

原本的思路大概是这样的吧,判断根节点值是否比左子节点的值大且比右子节点的值小,若成立,递归判断左子右子。不成立返回false,代码就不贴了。

想了一下,如果下面这样的树是不是也判定为二叉排序树,但是根据定义,这不是一个二叉排序树。。。

下面来看定义,百度就有。。

二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

在网上搜了一下,一个比较合适的思路就是设定一个左边界和一个右边界来判断,代码比较简单

节点定义为:

class TreeNode{
    public int value;
    public TreeNode left;
    public TreeNode right;
}

判断的函数如下:

public boolean judge(TreeNode p,int leftbound,int rightbound){
        if(p==null)
            return true;
        if(p.value<=leftbound||p.value>=rightbound)
            return false;
        if(!judge(p.left, leftbound, p.value))
            return false;
        if(!judge(p.right, p.value, rightbound))
            return false;
        return true;
    }

调用时:judge(head, Integer.MIN_VALUE, Integer.MAX_VALUE);