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 heapqclass Node:def __init__(self, weight, left=None, right=None):self.weight = weightself.left = leftself.right = right# 计算节点高度：叶子节点高度为0，父节点高度为子节点最大高度+1if left is None and right is None:self.height = 0else:self.height = max(left.height, right.height) + 1# 定义节点比较规则：先比权值，权值相同比高度def __lt__(self, other):if self.weight != other.weight:return self.weight < other.weightelse:return self.height < other.heightdef 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,