递归遍历Huffman Tree为叶子节点字符生成二进制编码的问题咨询

问题原因 #

你的代码存在两个逻辑错误，导致只能遍历到单条路径的叶子节点：

1. 非叶子节点的分支遍历用了else if，只要左子节点存在，右子节点的遍历逻辑就永远不会执行，相当于直接放弃了整棵树的右半部分遍历，自然只能得到最左路径的唯一一个叶子节点编码。
2. 你在当前方法作用域内修改了字符串s的取值，遍历完左子树后s已经追加了0，如果此时直接遍历右子树，会把左子树追加的0也带到右子树的编码里，导致编码错误。

修复方案 #

调整非叶子节点的分支判断逻辑，同时直接在传参时拼接编码字符串，不修改当前作用域的s值即可：

private String[] pathsToLeaves(Node r) {
    String[] array = new String[128];
    pathsToLeaves(r, array, "");
    return array;
}

private String[] pathsToLeaves(Node r, String[] array, String s) {
    // 到达叶子节点，存储编码
    if(r.data != (char)128) {
        array[r.data] = s;
        return array;
    }
    // 非叶子节点，左右子树都要遍历，分别传拼接后的编码参数
    if(r.left != null) {
        pathsToLeaves(r.left, array, s + "0");
    }
    if(r.right != null) {
        pathsToLeaves(r.right, array, s + "1");
    }
    return array;
}

原理解释 #

递归本身天然就会在子调用结束后回到上层节点，不需要你手动回到根节点：

• 每次遍历左子树时，传的是当前编码加0的新字符串，不会影响当前层级的s值
• 左子树递归结束后，自动回到当前非叶子节点，继续用原本的s值加1遍历右子树
• 所有路径都会被完整遍历，不会重复也不会遗漏，每个叶子节点的编码都会正确存储到对应下标位置

内容的提问来源于stack exchange，提问作者WeekendJedi