首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >二叉树是BST -为什么一个可以工作而另一个不能

二叉树是BST -为什么一个可以工作而另一个不能
EN

Stack Overflow用户
提问于 2014-11-30 18:09:57
回答 3查看 37关注 0票数 2

我正在尝试检查给定的Binary Tree是否是Binary Search Tree。我正在使用in order遍历来做到这一点。其思想是在按顺序遍历树时,在每个节点检查节点值是否大于前一次访问的noe的值。如果不是,那么它就不是BST。

我的问题是,为什么他的前两个工作,而不是第三个:

代码语言:javascript
复制
// This works - Implementation 1
--------------------------------
class PrevWrapper
{
    int data = Integer.MIN_VALUE;
}

public boolean isBST()
{
    return isBST(root, new PrevWrapper());
}

private boolean isBST(Node node, PrevWrapper previousElement)
{
    if ( node == null )
    {
        return true;
    }

    if ( !isBST(node.left, previousElement) )
    {
        return false;
    }

    if ( previousElement.data > node.item )
    {
        return false;
    }

    previousElement.data = node.item;
    return isBST(node.right, previousElement);
}

// This works - Implementation 2
--------------------------------
static int lastValue = Integer.MIN_VALUE;

static boolean isBST(Node root)
{
    if ( root == null )
    {
        return true;
    }
    if ( ! isBST(root.left) )
    {
        return false;
    }
    if ( root.item < lastValue )
    {
        return false;
    }
    lastValue = root.item;
    return isBST(root.right);
}

// This does not work - Implementation 3
--------------------------------

private boolean isBST(Node node, Integer previousElement)
{
    if ( node == null )
    {
        return true;
    }

    if ( !isBST(node.left, previousElement) )
    {
        return false;
    }

    if ( previousElement > node.item )
    {
        return false;
    }

    previousElement = node.item;
    return isBST(node.right, previousElement);
}

请解释一下。为什么我不能在函数调用桩上传递一个将维护状态的整数?或者是我在实现上做错了什么。

EN

Stack Overflow用户

发布于 2014-11-30 18:17:25

在最新的实现中,这段代码并没有像您预期的那样工作:

代码语言:javascript
复制
if ( previousElement > node.item )
{
    return false;
}

这里的previousElement应该具有左子树最右侧的叶节点的值,但实际上它具有父节点的值。

票数 0
EN
查看全部 3 条回答
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/27212106

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档