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

Question

这是我编写的用于打印二叉树从根到叶的所有路径的代码:

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);

}

我在 main 中调用这个方法是这样的:

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>());

}

我得到结果:

[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]

我应该修复什么才能使这项工作正常进行？我知道这类似于 this ，但我无法遵循该答案。谢谢。

Answer 1

问题是您没有删除元素，所以您沿着树的一侧向下移动，填满列表，然后向下移动另一侧，旧元素仍然存在。

删除元素的未经测试的代码:

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);
        // cast so we don't remove by index (would happen if 'data' is an int)
        list.remove((Integer)root.data);
        return;
    }

    printRootToLeaf(root.left, list);
    printRootToLeaf(root.right, list);
    // cast so we don't remove by index  (would happen if 'data' is an int)
    list.remove((Integer)root.data);
}

remove(Object) 不是特别有效，使用 LinkedList 然后使用 removeLast() 可能是个好主意。