(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

行：

path[idx] = r.val;

和

path.add(r.val);

不等价。

结果是第一个路径之后的后续路径被添加到列表的末尾。当您打印 path 时，这些不会被看到，因为您最多只打印 idx 个元素。

我不相信 Java 中有直接等效于数组赋值的列表。

呼叫

path.set(idx, r.val);

不起作用，因为 Java 不会自动增加列表。

通话中

path.add(idx, r.val);

也没有真正起作用，因为它将现有元素向右移动。

如果你想使用列表，我认为你必须在打印后清除它。

Answer 2

不同之处在于 idx 和 int 是按值传递的。但是，ArrayList path 是一个对象；因此，虽然作为引用的参数按值传递，但 path 引用的对象不是按值传递，而是在递归方法的所有调用之间共享。

这意味着在你的第一个方法中，当你递归调用它时：

    printDFS(r.left,  path, idx);
    printDFS(r.right, path, idx);

假设在 r.left 上调用 printDFS 时 idx 为 3。当递归方法用 idx++ 递增 idx 时，它们正在递增 idx 的新副本。因此，当递归方法最终结束并且 return 时，此方法使用的 idx 的副本仍然是 3，因此它将调用 printDFS(r.right, path, 3)。这会有所不同，因为您使用 idx 设置 path[idx].

在你的第二种方法中，idx 的行为方式相同，但你在构建 ArrayList 时没有使用它。相反，您添加到 ArrayList。所以当你打电话给

    printDFS(r.left,  path, idx);
    printDFS(r.right, path, idx);

现在，如果在 r.left 上调用 printDFS 时 path 有 3 个元素，当递归调用结束并且 return 时，它们已添加到 ArrayList--并且由于此对象在所有递归调用之间共享，因此 path 仍将包含递归调用添加到其中的所有元素。因此，与第一个代码示例不同，您调用 printDFS(r.right...) 的值与调用 printDFS(r.left...).

的值不同

有几种方法可以解决这个问题：

使用 idx 设置数组元素，正如另一个答案所建议的那样。但是，您需要检查 idx 是否是现有元素的索引，如果元素存在则使用 set 或如果 idx 等于 [=42= 则使用 add ].
在调用 each printDFS 之前复制 path。这确保所有递归调用都有自己的数组干净副本。（或者在 printDFS 的开头制作一个副本并使用它而不是原始路径；这应该确保没有 printDFS 修改其调用者的 path。）
确保每个 printDFS 离开 path 时的样子。因此，由于 printDFS 将一个新元素添加到数组的末尾，使其删除数组中在它 return 之前的最后一个元素。（我相信这会奏效，虽然我还没有测试过。但是，我一般不推荐这种方法；在更复杂的递归情况下，获得正确的 "cleanup" 可能非常困难。）

Answer 3

我遵循了 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;
        }
      }
    }

(java) DFS遍历中奇怪的List值

(java) weird List value in DFS traversal

java

tree

traversal

arraylist

microsoft-distributed-file-system