在二叉树中打印所有根到叶子路径

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)在所有方法调用中使用单个对象,这意味着,当您返回到原始调用者时,该对象与其状态不同.

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

Answer 2

你递归地传递你的列表,但这是一个可变对象,所以所有的调用都会修改它(通过调用List.add)并破坏你的结果.尝试将path参数克隆/复制到所有递归调用,以便为每个分支(harhar)提供自己的上下文.

Answer 3

public void PrintAllPossiblePath(Node node,List<Node> nodelist)
{
    if(node != null)
    {
            nodelist.add(node);
            if(node.left != null)
            {
                PrintAllPossiblePath(node.left,nodelist);
            }
            if(node.right != null)
            {
                PrintAllPossiblePath(node.right,nodelist);
            }
            else if(node.left == null && node.right == null)
            {

            for(int i=0;i<nodelist.size();i++)
            {
                System.out.print(nodelist.get(i)._Value);
            }
            System.out.println();
            }
            nodelist.remove(node);
    }
}

nodelist.remove(node) 是关键,它打印相应的路径后删除元素