打印二叉树中的所有根到叶路径 [英] print all root to leaf paths in a binary tree

问题描述

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

i am trying to print all root to leaf paths in a binary tree using 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());

但它给出了错误的输出.

But its giving wrong output.

给定的树:

   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]

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

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

有人能弄明白吗...

推荐答案

调用递归方法:

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

当你传递 path(而不是 new ArrayList(path) 是你在所有方法调用中使用单个对象时会发生什么，这意味着，当当你返回到原来的调用者时，对象的状态和原来不同了.

What happens there when you pass the path (instead of new ArrayList(path) is that you use a single object in all methods call, which means that, when you return to the original caller, the object is not in the same state as it was.

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

You just need to create a new object and initialize it to the original values. This way the original object does not get modified.

这篇关于打印二叉树中的所有根到叶路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！