DFS遍历中的(java)奇怪列表值

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

区别在于 idx int ,按值传递。然而 ArrayList path 是一个物体;因此,虽然作为引用的参数是通过值传递的,但 引用不是通过值传递的,而是在递归方法的所有调用之间共享的。

这意味着在第一个方法中,当递归调用时:

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

认为 你打电话的时候是3 printDFS 在…上 r.left idx++ ,他们正在增加 idx公司 该方法使用的仍然是3,因此它将调用 printDFS(r.right, path, 3) 设置 path[idx] .

在第二种方法中, 行为方式相同,但在构建 。相反,您将添加到

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

现在,如果 路径 在…上 r、 左 阵列列表 仍将包含递归调用添加到其中的所有元素。因此,与第一个代码示例不同,您没有调用 printDFS(r.right...) 与您调用的值相同 printDFS(r.left...) .

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

1. idx公司 idx公司 set add 如果 path.size() .

2. 路径 通话前 打印DFS 。这确保了所有递归调用都有自己的数组的干净副本。(或在 打印DFS 然后用它来代替原来的路径;这应该确保没有 修改调用者的 路径

3. 确保每个 打印DFS 路径 打印DFS 在数组末尾添加新元素,使其在返回之前删除数组的最后一个元素。(我相信这会奏效,尽管我还没有测试过它。但是,我一般不推荐这种方法;对于更复杂的递归情况,正确地进行“清理”可能非常困难。)

path[idx] = r.val;

path.add(r.val);

不等同。

结果是,第一条路径之后的后续路径被添加到列表的末尾。当您打印 path idx 元素。

使命感

path.set(idx, r.val);

因为Java不会自动增加列表,所以不起作用。

使命感

path.add(idx, r.val);

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