java - 无法在递归调用中设置引用变量

Question

我正在使用递归方法使用键在二叉树中查找节点。当我找到节点时，我将它设置为我的引用变量 foundNode 并返回。问题是，当我读取对象时，它的值仍然是 null。有人可以帮忙吗？

findGivenNode(root, key, foundNode, parentStack);

private boolean findGivenNode(Node node, int key, Node foundNode, Stack<Node> parentStack) {
    if (node == null) {
        return false;
    }

    parentStack.add(node);
    if (node.getData() == key) {
        foundNode = node;
        return true;
    }  
    boolean leftReturn = findGivenNode(node.getLeftChild(), key, foundNode, parentStack);
    boolean RightReturn = findGivenNode(node.getRightChild(), key, foundNode, parentStack);        
    if (leftReturn || RightReturn) {
        return true;
    }  else {
        parentStack.pop();
        return false;
    }
}

Answer 1

Java 不按引用传递参数，它们按值传递。 Read more here

让我们通过一个例子来说明。将您要查找的键设为值为 21 的整数。 函数开头的情况是这样的:

所以现在，当你说:

foundNode = node; // this doesn't reflect outside of the method

您正在 findGivenNode() 方法内部本地更改 foundNode 的值，它不适用于此方法之外。基本上，名为 foundNode 的局部变量引用您要更改的节点，然后您通过上面的语句使此局部变量 foundNode 引用新节点。 此更改仅反射(reflect)在函数内部。一旦您的函数完成，局部变量就不再存在，因此 foundNode 的本地版本也不存在。视觉效果:

简单的解决方案是使用 Wrapper function

要跟踪引用，您可以创建一个简单的包装类来存储您想要的引用:

private class NodeWrapper {
    Node foundNode;
    NodeWrapper() {
        foundNode = null;
    }
}

然后您可以创建一个新的 NodeWrapper 并将其传递给您的函数而不是 foundNode

NodeWrapper wrapper = new NodeWrapper();
findGivenNode(root, wrapper, key, parentStack);

然后在你的函数中而不是:

foundNode = node;

你说:

wrapper.foundNode = node;

这样您就可以在 NodeWrapper 中的整个递归过程中维护引用。含义:

NodeWrapper wrapper = new NodeWrapper();
findGivenNode(root, wrapper, key, parentStack);
// at this point, wrapper.foundNode will hold the reference to the node you need
// or null if the node wasn't found

另一方面，在方法之上你有这个函数原型(prototype):

findGivenNode(root, key, foundNode, parentStack);

好像有人还在用C/C++ :)

这在Java中是不必要的，你可以阅读this question thread了解其背后的原因或只是谷歌它。