java - 为什么在级别顺序树遍历期间会在 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;   
    }
}

为什么当我将 res.add(temp) 留在第二个 while 循环中时，它返回的答案为:[[3],[9,20],[9, 20],[15,7],[15,7]]

但是当我将 res.add(temp) 放在第二个 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);
    }
}