我正在尝试检查给定的Binary Tree是否是Binary Search Tree。我正在使用in order遍历来做到这一点。其思想是在按顺序遍历树时,在每个节点检查节点值是否大于前一次访问的noe的值。如果不是,那么它就不是BST。
我的问题是,为什么他的前两个工作,而不是第三个:
// 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);
}请解释一下。为什么我不能在函数调用桩上传递一个将维护状态的整数?或者是我在实现上做错了什么。
发布于 2014-11-30 18:17:25
在最新的实现中,这段代码并没有像您预期的那样工作:
if ( previousElement > node.item )
{
return false;
}这里的previousElement应该具有左子树最右侧的叶节点的值,但实际上它具有父节点的值。
https://stackoverflow.com/questions/27212106
复制相似问题