java - (java) DFS遍历中的怪异List值

Question

我正在尝试解决一个问题:

Print all paths of a binary tree, from root to leaf.

我写了下面的代码，结果是正确的:

public void printPath(TreeNode root) {

    printDFS(root, new int[1000], 0);

}



private void printDFS(TreeNode r, int[] path, int idx){
    if (r == null) return;

    path[idx] = r.val;
    idx++;

    /* if it's leaf, print path: from root to leaf */
    if (r.left == null && r.right == null) 
        printOnePath(path, idx);

    else {
        /* go left, go right */
        printDFS(r.left,  path, idx);
        printDFS(r.right, path, idx);
    }
}


private void printOnePath(int[] path, int idx) {
    for (int i = 0; i < idx; i++) {
        System.out.print(path[i] + " ");
    }
    System.out.println();         
}

However,
when I tried to use ArrayList to store the path data, instead of int[].
This method becomes wrong.
And the output results really lost me.

public void printPath(TreeNode root) {

    printDFS(root, new ArrayList<Integer>(), 0);        

}

private void printDFS(TreeNode r, List<Integer> path, int idx){
    if (r == null) return;

    path.add( r.val );
    idx++;

    /* if it's leaf, print path: from root to leaf */
    if (r.left == null && r.right == null) 
        printOnePath(path, idx);

    else {
        /* otherwise: go left, go right */
        printDFS(r.left,  path, idx);
        printDFS(r.right, path, idx);
    }
}


private void printOnePath(List<Integer> path, int idx) {
    for (int i = 0; i < idx; i++) {
        System.out.print(path.get(i) + " ");
    }
    System.out.println();         
}

例如:

对于二叉树:

第一个 STDOUT 是:(正确) 10 5 3 3 10 5 3 -2 10 5 2 1 10 -3 11

第二个 STDOUT 是:(错误) 10 5 3 3 10 5 3 3 10 5 3 3 10 5 3

我相信初始 ArrayList 已经在每个 DFS 的最开始设置为空。 为什么即使使用相同的方法，结果与 int 数组完全不同？

有人知道为什么吗？非常感谢!

Answer 1

我遵循了 ajb 提到的复制策略(此评论中的选项 #2)。这是修改后的代码。

    import apple.laf.JRSUIUtils;

    import java.util.ArrayList;
    import java.util.List;

    /**
     * Created by anilwaddi on 8/1/17.
     */
    public class DFSTest {


      public static void main(String args[]) throws Exception {

        DFSTest test = new DFSTest();
        test.printDFS();
    /*
    10 5 3 3
    10 5 3 -2
    10 5 2 1
    10 -3 11
     */
      }

      TreeNode root;

      DFSTest() {
        TreeNode node41 = new TreeNode(3, null, null);
        TreeNode node42 = new TreeNode(-2, null, null);
        TreeNode node43 = new TreeNode(1, null, null);


        TreeNode node31 = new TreeNode(3, node41, node42);
        TreeNode node32 = new TreeNode(2, node43, null);
        TreeNode node33 = new TreeNode(11, null, null);

        TreeNode node21 = new TreeNode(5, node31, node32);
        TreeNode node22 = new TreeNode(-3, node33, null);
        root = new TreeNode(10, node21, node22);
      }

      public void printDFS() {
        printPath(root);
      }

      public void printPath(TreeNode root) {
        printDFS(root, new ArrayList<Integer>());

      }

      private void printDFS(TreeNode r, List<Integer> path ) {
        if (r == null) return;

        path.add(r.val);

        /* if it's leaf, print path: from root to leaf */
        if (r.left == null && r.right == null)
          printOnePath(path );

        else {
            /* otherwise: go left, go right */
          List<Integer> newPathLeft = new ArrayList<>();
          newPathLeft.addAll(path);
          printDFS(r.left, newPathLeft);

          List<Integer> newPathRight = new ArrayList<>();
          newPathRight.addAll(path);
          printDFS(r.right, newPathRight);
        }
      }


      private void printOnePath(List<Integer> path ) {
        for (int i = 0; i < path.size(); i++) {
          System.out.print(path.get(i) + " ");
        }
        System.out.println();
      }

      private class TreeNode {
        TreeNode left;
        TreeNode right;
        Integer val;

        TreeNode(Integer val) {
          this.val = val;
        }

        TreeNode(Integer val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
        }
      }
    }