3

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

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]

我应该解决什么问题才能完成这项工作？我知道这与此类似，但我无法遵循该答案。谢谢。

4

5 回答 5

3

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

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

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)不是特别有效，使用LinkedListthenremoveLast()可能是一个好主意。

于 2013-09-17T16:03:38.607 回答
1

这是一个更简单的例子。

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

与预期的结果

[1,2]
[1,3]

和实际结果

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

当你第一次调用 printRootToLeaf 时，List是空的。你给它加 1，然后调用printRootToLeaf左边的分支。在该调用中，您将 2 添加到列表中，然后 print [1,2]。然后您返回第一个调用，但2 仍在列表中！然后你调用printRootToLeaf正确的分支。在该调用中，您将 3 添加到列表中，然后打印[1,2,3]。

沿左分支递归时对列表所做的更改不应传播到沿右分支向下传递的列表。解决这个问题的最简单方法是每次都复制列表：

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

复制列表的实际方法将根据您使用的语言而有所不同。

于 2013-09-17T15:58:14.787 回答
1

这是一个 C# 实现。您需要创建一个新列表并将现有路径放在那里。

    public static void PrintRoot2Leaves(Node root, List<int> path)
    {
        if (root == null) { return; }
        path.Add(root.Value);
        if (root.Left == null && root.Right == null)
        {
            Console.WriteLine(string.Join(",", path));
            return;
        }
        else {
            PrintRoot2Leaves(root.Left, new List<int>(path));
            PrintRoot2Leaves(root.Right, new List<int>(path));
        }
    }
于 2017-03-25T03:47:25.550 回答
0

如果您有对父节点的引用，则以下代码可以打印路径：

public void printPaths(Node n) {
    if(n != null) {
        if(n.left == null && n.right == null) { // found a leaf node, go up the tree
            StringBuilder sb = new StringBuilder();
            sb.append(" ").append(n);
            Node p = n.parent;
            while(p != null) {
                sb.insert(0, " ").insert(1,p);
                p = p.parent;
            }
            System.out.println(sb);
        }
        printPaths(n.left);
        printPaths(n.right);
    }
}
于 2015-01-03T16:40:13.540 回答
0

这里的问题是您是如何获得解决方案的，而不是您是否获得了解决方案。性能是这里的关键。首先创建一个树对象..

class Node {

public Node left;
public Node right;
public Character val;

public Node(char val) {
    this.val = val;
}

获取列表中的所有路径..

public List<LinkedList<Node>> printPath(Node root) {

    if (root == null) return new ArrayList<LinkedList<Node>>();

    List<LinkedList<Node>> left = printPath(root.left);
    List<LinkedList<Node>> right = printPath(root.right);

    left.addAll(right);

    for (LinkedList<Node> lst : left) {
        lst.addFirst(root);
    }
    if(left.size()==0){
        LinkedList<Node> lst= new LinkedList<Node>();
        lst.add(root);
        left.add(lst);
    }
    return left;

}

现在打印所有路径..

  Node root = new Node('a');
    System.out.println(root.val);
    root.left = new Node('b');
    root.left.left = new Node('c');
    root.left.right = new Node('d');
    root.right = new Node('e');
    root.right.left = new Node('f');
    root.right.right = new Node('g');
    root.right.right.left = new Node('h');

    List<LinkedList<Node>> allPaths = wc.printPath(root);

    for (LinkedList<Node> lst : allPaths) {
        for (Node node : lst)
            System.out.print(node.val==null ? "-" : node.val);
        System.out.println();
    }
于 2017-07-13T20:23:47.860 回答