java - 打印二叉树中所有根到叶的路径

Question

我正在尝试使用 java 在二叉树中打印所有根到叶的路径。

public void printAllRootToLeafPaths(Node node,ArrayList path) 
{
    if(node==null)
    {
        return;
    }
    path.add(node.data);

    if(node.left==null && node.right==null)
    {
        System.out.println(path);
        return;
    }
    else
    {
        printAllRootToLeafPaths(node.left,path);
        printAllRootToLeafPaths(node.right,path);
    }      
}

在主要方法中:

 bst.printAllRootToLeafPaths(root, new ArrayList());

但是它给出了错误的输出。

给定的树:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

预期输出:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

但是产生的输出:

[5, 1, 3]

[5, 1, 3, 8, 6]

[5, 1, 3, 8, 6, 9]

有人能想出办法吗...

Answer 1

调用递归方法:

printAllRootToLeafPaths(node.left, new ArrayList(path));
printAllRootToLeafPaths(node.right, new ArrayList(path));

当您传递 path(而不是 new ArrayList(path))时发生的事情是您在所有方法调用中使用单个对象，这意味着，当您返回到原始调用者，该对象的状态与原来不同。

您只需要创建一个新对象并将其初始化为原始值。这样原始对象就不会被修改。