二叉树是BST -为什么一个可以工作而另一个不能
我正在尝试检查给定的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);
}请解释一下。为什么我不能在函数调用桩上传递一个将维护状态的整数？或者是我在实现上做错了什么。
回答 3
Stack Overflow用户
发布于 2014-11-30 18:18:06
虽然integer是Integer的包装类，但它是不可变的。因此，一旦设置，任何编辑都只会创建这种类型的新对象，就像String一样。因此，尽管实现3尝试更改下一行中的previousElement的值，并希望将其传递给其他递归调用，但由于Integer类的工作方式，它不会发生。
previousElement = node.item；
然而，在实现1中，您为整数创建了一个包装器，它将保持状态，因为该类在随后的递归调用中通过引用传递。
Stack Overflow用户
发布于 2014-11-30 18:17:25
在最新的实现中，这段代码并没有像您预期的那样工作：
if ( previousElement > node.item )
{
return false;
}这里的previousElement应该具有左子树最右侧的叶节点的值，但实际上它具有父节点的值。
Stack Overflow用户
发布于 2014-11-30 18:17:36
如果您将一个整数作为参数传递给下一次isBST的递归调用，它将成为该方法的局部变量，并且递归方法的调用者在返回时不会看到对它所做的任何赋值。
这种行为是由于Java是一种通过值传递的语言造成的。当您将引用类型传递给某个方法时，该方法将获得该引用的本地副本。它只能通过更改其状态的方法来更改该引用所引用的实例的状态(假设它是可变的)。这就是在有PrevWrapper参数的版本中要做的事情。
https://stackoverflow.com/questions/27212106
复制相似问题
腾讯云开发者
