Why is my preorder traversal returning an empty list?-CodePudding

I am trying to understand why code is returning an empty list. I am not looking for a solution to the problem. The solution already exists in What is wrong with my Preorder traversal?

I want to understand, what is incorrect about my current understanding of recursion and the call stack upon using a global variable.

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);
    }
}

For the following tree : [1,null,2,3]

I notice that in the first print call I get 7 empty lists

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

In my second print call, I get the following

[1]
[2]
[3]

Why isn't my global variable list not "saving" or "appending" to the next call stack? It seems like, there are multiple list objects being utilized.

CodePudding user response：

Because you use preorderTraversal with left and right nodes so each time it will override list value with a new empty list, you should use preOrder with left and right node like this

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