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,