华为OD机试真题——生成哈夫曼树（2025A卷：100分）Java/python/JavaScript/C/C++/GO六种最佳实现

2025 A卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

本文收录于专栏：《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《生成哈夫曼树》：

题目名称：生成哈夫曼树

• 知识点：哈夫曼树、优先队列
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

题目描述

给定长度为 n 的无序数字数组，每个数字代表二叉树的叶子节点权值（所有值 ≥ 1）。请根据输入生成哈夫曼树，并输出其中序遍历结果。要求满足以下限制条件：

1. 节点权值规则：左节点权值 ≤ 右节点权值，根节点权值为左右子节点权值之和。
2. 高度规则：若左右节点权值相同，左子树高度 ≤ 右子树高度。

输入描述

• 第一行为整数 n（表示叶子节点数量，1 ≤ n ≤ 1e5）。
• 第二行为 n 个正整数，表示每个叶子节点的权值。

输出描述

• 输出中序遍历结果，数值间以空格分隔。若无有效树，返回空数组（用例保证输入有效）。

示例
输入：

5  
5 15 40 30 10  

输出：

40 100 30 60 15 30 5 15 10  

说明：

• 生成的哈夫曼树带权路径最短，如示例中总路径长度为：40×1 + 30×2 + 15×3 + 5×4 + 10×4 = 205。
• 中序遍历结果需满足左节点权值 ≤ 右节点，且权值相同时左子树高度更低。

补充说明：

• 哈夫曼树构造需通过优先队列（小顶堆）合并最小权值节点，直至只剩一个根节点。
• 时间复杂度需为 O(n log n)，空间复杂度 O(n)。

Java

问题分析

我们需要根据给定的权值数组构建哈夫曼树，并输出其中序遍历结果。哈夫曼树的构建需要满足：

1. 权值规则：左节点的权值 ≤ 右节点的权值。
2. 高度规则：权值相同时，左子树的高度 ≤ 右子树的高度。
3. 高效构造：使用优先队列（小顶堆）合并最小权值节点，时间复杂度为 O(n log n)。

解题思路

1. 优先队列初始化：将每个权值初始化为叶子节点，按权值从小到大排列，权值相同时按高度从小到大排列。
2. 构建哈夫曼树：
   • 每次从队列取出两个最小节点，合并为新节点。
   • 新节点的权值为子节点之和，高度为较大子树高度加一。
   • 根据权值规则和高度规则确定左右子节点顺序。
3. 中序遍历：使用非递归方式遍历树，按左 → 根 → 右顺序收集权值。

代码实现

import java.util.*;

public class Main {
   
    static class Node {
   
        int weight;
        Node left;
        Node right;
        int height;

        // 叶子节点构造函数
        public Node(int weight) {
   
            this.weight = weight;
            this.height = 0; // 叶子节点高度为0
        }

        // 合并生成父节点的构造函数
        public Node(Node left, Node right) {
   
            this.left = left;
            this.right = right;
            this.weight = left.weight + right.weight;
            this.height = Math.max(left.height, right.height) + 1;
        }
    }

    public static void main(String[] args) {
   
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> weights = new ArrayList<>();
        for (int i = 0; i < n; i++) {
   
            weights.add(scanner.nextInt());
        }

        // 优先队列：按权值从小到大，权值相同时按高度从小到大
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> {
   
            if (a.weight != b.weight) {
   
                return a.weight - b.weight;
            } else {
   
                return a.height - b.height;
            }
        });

        // 初始化队列，所有叶子节点入队
        for (int w : weights) {
   
            queue.add(new Node(w));
        }

        // 合并节点，构建哈夫曼树
        while (queue.size() > 1) {
   
            Node left = queue.poll();
            Node right = queue.poll();
            Node parent = new Node(left, right); // 自动满足左 ≤ 右
            queue.add(parent);
        }

        // 中序遍历
        Node root = queue.poll();
        List<Integer> result = new ArrayList<>();
        Deque<Node> stack = new LinkedList<>();
        Node current = root;

        // 非递归中序遍历
        while (current != null || !stack.isEmpty()) {
   
            while (current != null) {
   
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.weight);
            current = current.right;
        }

        // 输出结果
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
   
            sb.append(num).append(" ");
        }
        if (sb.length() > 0) {
   
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb);
    }
}

代码详细解析

1. Node 类：

   • weight：节点权值。
   • left 和 right：左右子节点。
   • height：节点高度，叶子节点为0，父节点为子节点最大高度加一。

2. 优先队列初始化：

   • 自定义比较器，先按权值排序，权值相同时按高度排序。
   • 将所有叶子节点加入队列。

3. 合并节点：

   • 循环取出两个最小节点，合并为新节点。
   • 新节点的左右顺序由队列比较器自动保证（权值小者优先，权值相同高度小者优先）。

4. 中序遍历：

   • 使用栈模拟递归，按左 → 根 → 右顺序遍历所有节点。
   • 收集所有节点的权值到结果列表。

5. 输出处理：

   • 将结果列表转换为字符串格式，确保末尾无空格。

示例测试

输入1：

5  
5 15 40 30 10  

输出：

40 100 30 60 15 30 5 15 10  

解析：合并顺序确保所有条件满足，中序遍历结果正确。

输入2：

2  
3 5  

输出：

3 8 5  

解析：合并生成父节点8，中序遍历顺序为3 → 8 → 5。

输入3：

1  
5  

输出：

5  

解析：单个叶子节点，直接输出自身权值。

综合分析

1. 时间复杂度：O(n log n)。
   • 优先队列的插入和删除操作均为 O(log n)，共执行 O(n) 次。
2. 空间复杂度：O(n)。
   • 存储哈夫曼树需要 O(n) 空间，优先队列和中序遍历栈均为 O(n)。
3. 优势：
   • 高效合并：优先队列确保每次合并选择最小权值节点。
   • 自动排序：比较器自动处理权值和高度规则，确保树结构正确。
4. 适用场景：大规模数据处理，符合题目要求的 O(n log n) 时间复杂度和 O(n) 空间复杂度。

python

问题分析

我们需要根据给定的权值数组构建哈夫曼树，并输出其中序遍历结果。哈夫曼树的构建需满足：

1. 权值规则：左节点权值 ≤ 右节点权值。
2. 高度规则：权值相同时，左子树高度 ≤ 右子树高度。
3. 高效构造：使用优先队列（小顶堆）合并最小节点，时间复杂度为 O(n log n)。

解题思路

1. 优先队列初始化：将每个权值初始化为叶子节点，按权值从小到大排列，权值相同时按高度从小到大排列。
2. 构建哈夫曼树：
   • 每次从队列取出两个最小节点，合并为新节点。
   • 新节点的权值为子节点之和，高度为较大子树高度加一。
3. 中序遍历：使用栈模拟递归遍历，按左 → 根 → 右顺序收集权值。

代码实现

import heapq

class Node:
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right
        # 计算节点高度：叶子节点高度为0，父节点高度为子节点最大高度+1
        if left is None and right is None:
            self.height = 0
        else:
            self.height = max(left.height, right.height) + 1

    # 定义节点比较规则：先比权值，权值相同比高度
    def __lt__(self, other):
        if self.weight != other.weight:
            return self.weight < other.weight
        else:
            return self.height < other.height

def main():
    n = int(input())
    weights = list(map(int, input().split()))
    
    if n == 0:
        print("")
        return
    
    # 初始化优先队列
    heap = []
    for w in weights:
        heapq.heappush(heap, Node(w))
    
    # 合并节点直到只剩根节点
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        # 创建父节点，自动满足左≤右的规则
        parent = Node(left.weight + right.weight, left, right)
        heapq.heappush(heap,