Java Binary InOrder Tree Traversal - 为什么在函数外部初始化 ArrayList 会

Question

我写了一个递归函数，将二叉树的所有节点添加到整数类型的列表中，但由于某种原因，它一直给我带来问题。这是我的代码最初的样子：

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
public void helper(TreeNode root, List<Integer> res){
if(root == null){
return;
}
inorderTraversal(root.left);
res.add(root.val);
inorderTraversal(root.right);
}

然而，它一直失败，没有给我适当的解决方案。但事实证明，如果从"inorderTraversal"函数中取出第一行并使其全局化，则此代码有效：

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

有人可以向我解释为什么这会有所作为以及为什么它最初失败吗？

Answer 1

因为您以递归方式调用"inorderTraversal"，所以每次调用该方法时，它都会覆盖"res"并创建一个新对象。因此，"res"必须是全局的，以防止发生这种覆盖。

Answer 2

我也遇到了同样的问题，问题是你在 inorderTraversal(( 上使用递归。 你应该在帮助程序方法本身上使用递归，因为帮助程序方法的作用反映在 inorderTraversal(( 上。 代码如下。

public void helper(TreeNode root, List<Integer> ans){
if(root != null){
helper(root.left, ans);
ans.add(root.data);
helper(root.right, ans);
}
}