恢复哈夫曼树

[题目链接](https://www.nowcoder.com/practice/9f97544aa62e40288a6267ad83262047)

思路

本题给定一棵哈夫曼树所有叶子节点的哈夫曼编码（0 表示左、1 表示右），以及叶子节点的权值集合（顺序随机），要求恢复出完整的哈夫曼树。

关键观察

哈夫曼树有三条排序约束：

  1. 权值越小的叶子越深——较小的权值应被分配到编码更长（层数更深）的位置。
  2. 同层节点权值从左到右递增——同一深度的叶子，左边的权值不大于右边的。
  3. 左子节点权值 右子节点权值——这一条在叶子正确分配后，内部节点由子节点权值之和确定，自动满足。

做法

分三步完成：

第一步：建树骨架。 根据每个叶子的哈夫曼编码，从根节点出发，遇 0 走左、遇 1 走右，逐步创建节点，最终到达叶子位置。所有编码处理完后，树的形状就确定了。

第二步：分配权值。 将叶子按 (深度降序, 同深度按编码字典序升序) 排列，将权值升序排列，一一对应赋值。这样最小的权值分配给最深且最靠左的叶子，满足上述约束。

第三步：填充内部节点。 后序遍历整棵树，每个内部节点的值等于其左右子节点值之和。

样例演示

输入 leaf = ["0","10","11"]，value = [2,1,2]。

编码 深度 排序优先级
"10" 2 最高（最深）
"11" 2 次高（同深度，字典序更大）
"0" 1 最低（最浅）

权值升序排列：[1, 2, 2]。

分配结果："10" → 1，"11" → 2，"0" → 2。

填充内部节点后，右子节点值 = 1 + 2 = 3，根节点值 = 2 + 3 = 5。

输出：{5, 2, 3, #, #, 1, 2}。

复杂度

  • 时间复杂度：，其中 为叶子节点数， 为所有编码长度之和。排序 ，建树 。
  • 空间复杂度：，用于存储树节点。

代码

class Solution {
public:
    TreeNode* recoverHuffman(vector<string>& leaf, vector<int>& value) {
        int n = leaf.size();
        TreeNode* root = new TreeNode(0);
        vector<TreeNode*> leafNodes(n);

        // 根据编码建树骨架
        for (int i = 0; i < n; i++) {
            TreeNode* cur = root;
            for (char c : leaf[i]) {
                if (c == '0') {
                    if (!cur->left) cur->left = new TreeNode(0);
                    cur = cur->left;
                } else {
                    if (!cur->right) cur->right = new TreeNode(0);
                    cur = cur->right;
                }
            }
            leafNodes[i] = cur;
        }

        // 按深度降序、同深度按编码字典序升序排列
        vector<int> indices(n);
        for (int i = 0; i < n; i++) indices[i] = i;
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            if (leaf[a].size() != leaf[b].size())
                return leaf[a].size() > leaf[b].size();
            return leaf[a] < leaf[b];
        });

        // 权值升序排列后一一分配
        sort(value.begin(), value.end());
        for (int i = 0; i < n; i++) {
            leafNodes[indices[i]]->val = value[i];
        }

        // 后序遍历填充内部节点
        fillValues(root);
        return root;
    }

private:
    int fillValues(TreeNode* node) {
        if (!node->left && !node->right) return node->val;
        int sum = 0;
        if (node->left) sum += fillValues(node->left);
        if (node->right) sum += fillValues(node->right);
        node->val = sum;
        return sum;
    }
};

import java.util.*;

public class Solution {
    public TreeNode recoverHuffman(String[] leaf, int[] value) {
        TreeNode root = new TreeNode(0);
        int n = leaf.length;
        TreeNode[] leafNodes = new TreeNode[n];

        // 根据编码建树骨架
        for (int i = 0; i < n; i++) {
            String code = leaf[i];
            TreeNode cur = root;
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    if (cur.left == null) cur.left = new TreeNode(0);
                    cur = cur.left;
                } else {
                    if (cur.right == null) cur.right = new TreeNode(0);
                    cur = cur.right;
                }
            }
            leafNodes[i] = cur;
        }

        // 按深度降序、同深度按编码字典序升序排列
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> {
            int da = leaf[a].length();
            int db = leaf[b].length();
            if (da != db) return db - da;
            return leaf[a].compareTo(leaf[b]);
        });

        // 权值升序排列后一一分配
        int[] sortedValues = Arrays.copyOf(value, n);
        Arrays.sort(sortedValues);
        for (int i = 0; i < n; i++) {
            leafNodes[indices[i]].val = sortedValues[i];
        }

        // 后序遍历填充内部节点
        fillValues(root);
        return root;
    }

    private int fillValues(TreeNode node) {
        if (node.left == null && node.right == null) return node.val;
        int sum = 0;
        if (node.left != null) sum += fillValues(node.left);
        if (node.right != null) sum += fillValues(node.right);
        node.val = sum;
        return sum;
    }
}