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

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

2024-07-04 08:00:07   221人阅读

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

原本的思路大概是这样的吧，判断根节点值是否比左子节点的值大且比右子节点的值小，若成立，递归判断左子右子。不成立返回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);


联系
我们