为什么在级别顺序树遍历过程中返回2D列表中的重复项？

Question

这是leetcode问题#102。这个问题的leetcode描述是：给定一个二叉树，返回其节点值的级别顺序遍历。（即，从左到右，逐级）。

所以给一棵像树一样的树

    3
   / \
  9  20
    /  \
   15   7

应该返回

[
  [3],
  [9,20],
  [15,7]
]

我的代码在下面

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> list = new LinkedList<TreeNode>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        list.add(root);

        while(!list.isEmpty()){
            int size = list.size();
            List<Integer> temp = new ArrayList<Integer>();

            while(size != 0){

                root = list.remove();

                if(root.left != null)  list.add(root.left);
                if(root.right != null) list.add(root.right);

                temp.add(root.val);

                size--;
                res.add(temp);
            }
        }
        return res;   
    }
}

为什么当我在第二个while循环中离开res.add（temp）时，它返回的答案是：[[3]，[9,20]，[9,20]，[15,7]，[15,7]]

但是当我把res.add（temp）放在第二个while循环的外部，而放在第一个while循环的内部时，我得到了正确的答案。另外，如果这篇文章的格式很糟糕，或者如果我写这篇文章的时间比我应该写的要长很多，我也很抱歉，因为我还没有在stackoverflow上发布问题。非常感谢。

Answer 1

因为第一个循环通过级别（级别是list的当前内容）：

    3            one list for level 0: [3]
   / \           
  9  20          one list for level 1: [9, 20]
    /  \
   15   7        one list for level 2: [15, 7]  

第二个循环通过每个级别上的节点（root是当前节点）：

    3            one list for "3": [3]
   / \           
  9  20          one list for "9" [9, 20], the same list for "20": [9, 20]
    /  \
   15   7        one list for "15" [15, 7], the same list for "7" [15, 7]  

您可以输出list和root的当前值，以帮助您可视化算法：

while(!list.isEmpty()){
    System.out.println("First loop. Current level: "+list);
    int size = list.size();
    List<Integer> temp = new ArrayList<Integer>();
    while(size != 0) {
        root = list.remove();
        System.out.println("Second loop. Current node: "+root);

        if(root.left != null)  list.add(root.left);
        if(root.right != null) list.add(root.right);

        temp.add(root.val);
        size--;
        res.add(temp);
    }
}