哈夫曼编码压缩文本长度计算：递归函数优化与复杂度分析

嘿，我来帮你梳理下这个哈夫曼树递归函数的问题～

你之前认为的O(log2n)其实不太准确，我们先理清楚哈夫曼树的节点数量：假设文本里的不同字符种类数为k（也就是哈夫曼树的叶节点数），那么哈夫曼树的总节点数是2k-1——因为每次合并两个节点生成一个新节点，总共要合并k-1次，总节点数就是叶节点数加合并出来的节点数：k + (k-1) = 2k-1。

你的递归函数会遍历每一个节点一次：叶节点直接计算返回，非叶节点会递归处理左右子树，每个节点只会被访问一次。所以实际时间复杂度是O(k)（如果题目里的n指的是文本总字符数，那k≤n，复杂度也可以说是O(n)），是线性时间，不是对数级。

你的代码逻辑是正确的，但可以利用哈夫曼树的特性简化：哈夫曼树中不存在只有一个子节点的非叶节点。因为哈夫曼树的构建规则是每次选两个最小频率的节点合并，所以所有非叶节点一定同时有左右两个子节点，那些判断单孩子的分支完全是多余的，可以直接删掉，简化后的代码更清晰：

def get_length(node, depth):
    # 叶节点：返回字符频率乘以编码深度
    if node.left_child is None and node.right_child is None:
        return node.freq * depth
    # 非叶节点：必然有左右两个子节点，递归累加左右子树的结果
    return get_length(node.left_child, depth + 1) + get_length(node.right_child, depth + 1)

另外，如果要处理非常大规模的哈夫曼树，递归可能会遇到递归深度限制（比如极端情况下哈夫曼树的高度接近k，超过Python默认的递归深度阈值），这时候可以改成迭代版本，用栈来模拟递归过程，避免栈溢出问题：

def get_length_iterative(root):
    total_length = 0
    # 栈中存储(当前节点, 当前深度)的元组
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if node.left_child is None and node.right_child is None:
            total_length += node.freq * depth
        else:
            # 栈是后进先出，先压右子节点再压左子节点，保证遍历顺序和递归一致
            stack.append((node.right_child, depth + 1))
            stack.append((node.left_child, depth + 1))
    return total_length

迭代版的时间复杂度同样是O(k)，但稳定性更好，适合处理大规模数据。

用你给出的abaccab示例（字符频率a:3、b:2、c:2），优化后的函数计算结果：

• a的编码深度是1，贡献3*1=3
• b和c的编码深度是2，分别贡献2*2=4
  总和3+4+4=11，和你给出的结果完全一致，验证了代码的正确性。

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