为什么我的预序遍历返回一个空列表？

Question

我想了解为什么代码返回一个空列表。我不是在寻找问题的解决方案。该解决方案已存在于 What is wrong with my Preorder traversal?

我想了解一下，我目前对递归和使用全局变量的调用堆栈的理解有什么不正确的地方。

class Solution {
    ArrayList<Integer> list;
    public List<Integer> preorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        preOrder(root);
        return list;
    }
    public void preOrder(TreeNode node){
        System.out.println(list.toString());
        if(node == null)
            return;
        
        list.add(node.val);
        
        //System.out.println(list.toString());
        
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
}

对于以下树：[1,null,2,3]

我注意到在第一个打印调用中我得到 7 个空列表

[]
[]
[]
[]
[]
[]
[]

在我的第二次打印调用中，我得到以下信息

[1]
[2]
[3]

为什么我的全局变量列表没有“保存”或“附加”到下一个调用堆栈？好像有多个列表对象被利用了。

Answer 1

因为你对左右节点使用 preorderTraversal 所以每次它都会用一个新的空列表覆盖列表值，你应该像这样对左右节点使用 preOrder

public void preOrder(TreeNode node){
    if(node == null)
        return;
        
    list.add(node.val);
        
    preOrder(node.left);
    preOrder(node.right);
}

为什么我的预序遍历返回一个空列表？

Why is my preorder traversal returning an empty list?

java

recursion

binary-tree

preorder