二叉树递归中的哪些参数是局部的?

Question

import java.util.*;

public static void main(String[] args) {
TreeNode root = new TreeNode(8);
root.left = new TreeNode(7);
root.right = new TreeNode(6);
root.left.left = new TreeNode(5);
root.right.right = new TreeNode(4);
List<Integer> list = postorderTraversal(root);
System.out.println(list);
}
public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
list = helper(root, list);
return list;
}
private static List<Integer> helper(TreeNode node, List<Integer> list){
if (node != null) {
helper(node.left, list);
helper(node.right, list);
list.add(node.val);
}
return list;
}
}

在这个问题上，我不明白为什么我不必做list = helper(node.left, list);为什么list在这里是全局的，当我改变我的根时它是本地的，我必须做root.left = recurse(root.left)？

Answer 1

这是因为指针在 Java 中的工作方式。 当您将 list 作为参数传递给函数时，您不是在传入对象本身，而是在计算机上传入其内存地址。此内存地址称为指针，非常有用，因为它可以避免昂贵的重复对象。

你通常不会注意到这一点，因为Java通常会隐藏它使用指针的事实。例如，当你执行list.add(...)时，它的工作方式就像你使用一个普通对象并在其上调用add()，因为java会自动用指针替换对象。

所以 list 有点像一个全局变量，因为即使每次将指针传递到某个东西时都会被复制，它仍然引用同一段内存。更改内存的该部分将影响指向该位置的所有其他指针看到的内容，因此您可以获得其他函数可以看到的更改。

Answer 2

语句

List<Integer> list = new ArrayList<Integer>();

做两件事。 首先，它在堆上分配一个新的ArrayList对象。然后，它将对该堆对象的引用存储在局部变量list中。 当你调用helper时，你只传递引用，它可以被认为是一个内存地址，指的是堆上的实际对象。此引用将传递给helper的递归调用。每次调用都会获得list的本地副本，但这只是引用的副本，而不是堆对象的副本。 所有这些list实例都引用同一个堆对象，即您最初分配的堆对象。 这就是为什么它"感觉"像是全球性的，但绝对不是。

同样的概念适用于TreeNode引用，实际上适用于 Java 中的所有对象引用。

对于新的Java程序员来说，这可能会非常令人困惑。Java是"按值传递"，这意味着在调用方法时会复制参数，但是当变量是对象时，"值"是引用而不是对象本身，并且仅复制引用。 为参数传递而复制的唯一值是基元值(boolean、char、int、long、float、double)。