java - 二叉树的Level Order Traversal(具体题目见下方代码)

Question

在下面的代码中，为什么我需要这一行:

ArrayList<Integer> c_curr = new ArrayList<Integer>(curr);

为什么我不能直接将 curr 添加到结果 res 中？当我尝试这样做时，我得到一个空的资源。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null)
        return res;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root);
    q.add(null);
    ArrayList<Integer> curr = new ArrayList<Integer>();
    TreeNode t;
    while (!q.isEmpty()) {
        t = q.poll();

        if (t != null) {
            curr.add(t.val);
            if (t.left != null) {
                q.offer(t.left);
            }
            if (t.right != null) {
                q.offer(t.right);
            }
        } else {
            ArrayList<Integer> c_curr = new ArrayList<Integer>(curr);
            res.add(c_curr);
            curr.clear();
            if (!q.isEmpty())
                q.offer(null);
        }
    }
    return res;
}

Answer 1

假设我们像这样更改这些行:

//ArrayList<Integer> c_curr = new ArrayList<Integer>(curr);
//res.add(c_curr);
res.add(curr);
curr.clear();

列表 curr 添加到结果 res。 Java 按值传递参数。所以当你调用

boolean java.util.List.add(List<Integer> e)

方法，将curr的值复制到e。但是因为 curr 是一个对象，所以 curr 和 e 指的是内存中的同一个地方。因此，当您清除 curr 时，您会得到一个空的 res。

那是因为创建了一个新列表 c_curr，其值为 curr。然后添加到原代码中的res中。因此修改 curr 不会影响 res。