java - 二叉树层次顺序遍历调试

Question

我有这个二叉树

    3
   / \
  9  20
    /  \
   15   7

我想以这种格式打印其级别顺序遍历

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

所以我使用队列和两个列表编写了这段代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new LinkedList<>();
        if(root!=null)
        {
            queue.add(root);
        }

        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++)
            {

            TreeNode tempNode=queue.poll();
            list.add(tempNode.val);
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            }
            res.add(list);
            list.clear();

        }

        return res;

    }
}

但是当我检查输出时它会返回

[[],[],[]]

我花了 1 个多小时来调试这个问题，并且我确信我的代码是正确的(事实并非如此!)我不知道在将数据添加到 res 列表后，什么会清除它。请帮我修复错误。

我相信list.clear()也会清除res中添加的列表项。

假设是这样

x=34;
list.add(x);
x=45;
System.out.println(list); // it will still print [34]

但是使用列表列表并在向其中添加项目后，如果您修改内部列表..它也会修改您的列表列表。为什么？

int x=3;
li.add(x);
x=45;
res.add(li);
System.out.println(li);
li.remove(0);
li.add(23);
System.out.println(res);

Answer 1

发生这种情况是因为您正在操作对象，而不会发生在原始类型上

<小时/>

您正在使用单个list例如，在外部列表中添加列表后，您仍在操作相同的列表，您始终引用相同 List实例

您在外部列表中多次添加它并清除它，您需要在每次迭代时创建新实例:

while(!queue.isEmpty()){
    int size = queue.size();
    for(int i=0 ; i<size;i++){
        TreeNode tempNode = queue.poll();
        list.add(tempNode.val);
        if(tempNode.left!=null)
            queue.add(tempNode.left);
        if(tempNode.right!=null)
            queue.add(tempNode.right);
    }
    res.add(list);
    list = new ArrayList<>();
}