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

java tree binary-tree

2022-09-02 19:15:46

我正在尝试使用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, 3]

[5, 8, 6]

[5, 8, 9]

但输出产生：

[5, 1, 3]

[5, 1, 3, 8, 6]

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

有人能弄清楚吗...

答案 1

使用以下命令调用递归方法：

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

当您传递（而不是在所有方法调用中使用单个对象）时会发生什么情况，这意味着，当您返回到原始调用方时，该对象的状态与以前不同。pathnew ArrayList(path)

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

答案 2

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)是键，一旦它打印了相应的路径，它就会删除元素