打印从根的所有路径叶二叉树 [英] Print all paths from root to leaf in a Binary tree

问题描述

下面是code我写了打印二叉树的所有路径从根到叶：

Here is the code I wrote to print all paths of a Binary tree from root to leaf:

public static void printRootToLeaf(Node1 root, List<Integer> list) {
    if(root == null) {
        return;
    }

    list.add(root.data);

    if(root.left == null && root.right == null) {
        System.out.println(list);
        return;
    }

        printRootToLeaf(root.left, list);
        printRootToLeaf(root.right, list);

}

我打电话这种方法主要是这样的：

I am calling this method in main like this:

public static void main(String[] args) {

    Node1 root = new Node1(1);
    Node1 two = new Node1(2);
    Node1 three = new Node1(3);
    Node1 four = new Node1(4);
    Node1 five = new Node1(5);
    Node1 six = new Node1(6);
    Node1 seven = new Node1(7);
    Node1 eight = new Node1(8);

    root.left = two;
    root.right = three;
    two.left = four;
    two.right = five;
    three.left = six;
    three.right = seven;
    five.left = eight;

    printRootToLeaf(root, new ArrayList<Integer>());

}

我得到的结果是：

I get the result:

[1, 2, 4]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8, 3, 6]
[1, 2, 4, 5, 8, 3, 6, 7]

而我期待：

[1, 2, 4]
[1, 2, 5, 8]
[1, 3, 6]
[1, 3, 7]

我应该怎么解决，使这项工作？我知道这是类似<一个href="http://stackoverflow.com/questions/14936861/print-all-root-to-leaf-paths-in-a-binary-tree">this,但我无法跟随那个答案。谢谢你。

What should I fix to make this work? I know this is similar to this, but I am unable to follow that answer. Thanks.

推荐答案

下面是一个简单的例子。

Here is a simpler example.

Node1 root = new Node1(1);
root.left = new Node(2);
root.right = new Node(3);

随着预期的结果。

With the expected result

[1,2]
[1,3]

和实际效果

[1,2]
[1,2,3]

当你第一次叫printRootToLeaf，列表是空的。你把它加1，并调用 printRootToLeaf 左边分支。在这一号召，加2到列表中，并打印 [1,2] 。然后，返回到第一个呼叫，但 2还是在右侧分支名单！的你，然后调用 printRootToLeaf 。在这一号召，你加3到列表中，并打印 [1,2,3] 。

When you first call printRootToLeaf, List is empty. You add 1 to it, and call printRootToLeaf on the left branch. Within that call, you add 2 to the list, and print [1,2]. You then return to the first call, but 2 is still in the list! You then call printRootToLeaf on the right branch. Within that call, you add 3 to the list, and print [1,2,3].

发到列表中，而递归下降左支不应该传播到列表中的更改流传下来的右分支。解决这一问题的最简单方法是每次作列表的副本：

Changes made to the list while recursing down the left branch shouldn't propogate to the list passed down the right branch. The easiest way to address this is to make copies of the list each time:

printRootToLeaf(root.left, copy(list));
printRootToLeaf(root.right, copy(list));

复制列表将取决于什么语言你使用变化的实际方法。

The actual method of copying the list will vary depending upon what language you're using.

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