如何打印二叉树每个叶子的路径？

Question

在下面的二叉树中，除了叶节点之外，所有节点都是空的。我正在尝试将叶子输出为与其旁边的编码 table 相同。

对于这个方法，我有：

     public static void printCodes(MsgTree root, String encoding) {
    if (root.left == null && root.right == null) {
        System.out.println(root.payloadChar + " --is-- " + encoding);
    } else {
        if (root.left != null) {
            encoding += '0';
            printCodes(root.left, encoding);
        } if(root.right!=null) {
            encoding += '1';
            printCodes(root.right, encoding);
        }
    }
}

但是，这是我得到的输出：

a --is-- 0

！ --是-- 0100

d --is-- 010010

c --is-- 0100101

r --is-- 01010

b --is-- 010101

所以我认为我的问题与多余的 0 有关，如何更正它？

Answer 1

代码正在变异encoding，所以如果有两个子节点，转到左边的节点将保持0。

您可以保持 encoding 不变，例如：

public static void printCodes(MsgTree root, String encoding) {
    if (root.left == null && root.right == null) {
        System.out.println(root.payloadChar + " --is-- " + encoding);
    } else {
        if (root.left != null) {
            printCodes(root.left, encoding + '0');
        } if (root.right!=null) {
            printCodes(root.right, encoding + '1');
        }
    }
}

如何打印二叉树每个叶子的路径？

how to print paths to each leaf of binary tree?

java

recursion

binary-tree

data-structures