2025 A卷 200分 題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；

并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；

本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《二叉樹的廣度優先遍歷》：

---

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C

GO

---

題目名稱：二叉樹的廣度優先遍歷

---

1. 知識點：字符串處理、遞歸/分治算法（構建二叉樹）、隊列操作（BFS）
2. 時間限制：1秒
3. 空間限制：256MB
4. 限定語言：不限

---

題目描述

有一棵二叉樹，每個節點由一個大寫字母標識（最多26個節點）。現有兩組字母，分別表示后序遍歷（左孩子->右孩子->父節點）和中序遍歷（左孩子->父節點->右孩子）的結果，請輸出該二叉樹的層次遍歷結果。

輸入描述
輸入為兩個字符串，第一個字符串表示后序遍歷結果，第二個字符串表示中序遍歷結果。字符串僅包含大寫字母，且長度不超過26。

輸出描述
輸出二叉樹的層次遍歷結果，為一個連續字符串，無需分隔符。

示例
輸入：

CBEFDA CBAEDF

輸出：

ABDCEF

說明：
對應的二叉樹結構為：

    A  / \  B   D  /   / \  
C   E   F

層次遍歷順序為A→B→D→C→E→F。

---

Java

問題分析

題目要求根據后序和中序遍歷結果構建二叉樹，并輸出層次遍歷結果。關鍵在于如何正確分割后序和中序序列以遞歸構建樹。

---

解題思路

1. 構建二叉樹：
   • 后序的最后一個元素為根節點。
   • 在中序中找到根的位置，分割左、右子樹的中序序列。
   • 根據左子樹節點數，分割后序的左、右子樹部分。
2. 層次遍歷：使用隊列實現廣度優先遍歷，按層輸出節點。

---

代碼實現

import java.util.*;class TreeNode {char val;TreeNode left;TreeNode right;TreeNode(char x) { val = x; }
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String postOrder = scanner.next();String inOrder = scanner.next();char[] in = inOrder.toCharArray();char[] post = postOrder.toCharArray();TreeNode root = buildTree(in, post);String result = levelOrder(root);System.out.println(result);}// 構建二叉樹private static TreeNode buildTree(char[] in, char[] post) {return buildTreeHelper(in, 0, in.length - 1, post, 0, post.length - 1);}private static TreeNode buildTreeHelper(char[] in, int inStart, int inEnd, char[] post, int postStart, int postEnd) {if (inStart > inEnd || postStart > postEnd) return null;char rootVal = post[postEnd];TreeNode root = new TreeNode(rootVal);int rootPos = findRootPosition(in, inStart, inEnd, rootVal);int leftSize = rootPos - inStart;root.left = buildTreeHelper(in, inStart, rootPos - 1, post, postStart, postStart + leftSize - 1);root.right = buildTreeHelper(in, rootPos + 1, inEnd, post, postStart + leftSize, postEnd - 1);return root;}// 在中序數組中找到根的位置private static int findRootPosition(char[] in, int start, int end, char target) {for (int i = start; i <= end; i++) {if (in[i] == target) return i;}return -1;}// 層次遍歷private static String levelOrder(TreeNode root) {if (root == null) return "";Queue<TreeNode> queue = new LinkedList<>();StringBuilder sb = new StringBuilder();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();sb.append(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}return sb.toString();}
}

---

代碼詳解

1. TreeNode類：定義二叉樹的節點結構。
2. main方法：讀取輸入的后序和中序字符串，轉換為字符數組后構建樹，輸出層次遍歷結果。
3. buildTree方法：
   • 調用buildTreeHelper遞歸構建樹，參數為中序和后序數組的起始、結束索引。
   • 后序的最后一個元素為當前根節點。
   • 在中序數組中找到根的位置rootPos，計算左子樹節點數leftSize。
   • 遞歸構建左子樹和右子樹，分割后序數組的左右部分。
4. findRootPosition方法：遍歷中序數組，返回根的位置。
5. levelOrder方法：使用隊列實現層次遍歷，按層輸出節點。

---

示例測試

1. 輸入1：

   CBEFDA CBAEDF  
   

   輸出：

   ABDCEF  
   

   說明：構建的樹結構為A→B→D→C→E→F。

2. 輸入2：

   CEDBA CBEDA  
   

   輸出：

   ABDCE  
   

   說明：構建的樹結構為A→B→D→C→E。

3. 輸入3：

   CBA CBA  
   

   輸出：

   ABC  
   

   說明：構建的樹結構為A→B→C，層次遍歷順序為A→B→C。

---

綜合分析

1. 時間復雜度：

   • 構建樹：O(n^2)，每次遞歸需遍歷中序數組查找根位置。
   • 層次遍歷：O(n)，每個節點進出隊列一次。

2. 空間復雜度：

   • O(n)，存儲遞歸調用棧和隊列。

3. 正確性：

   • 通過索引精確分割數組，確保樹的結構正確。
   • 層次遍歷隊列保證節點按層輸出。

4. 優勢：

   • 索引分割：避免字符串切割錯誤，提高精度。
   • 隊列遍歷：簡單高效實現層次遍歷。

5. 適用性：

   • 支持最多26個節點的輸入，滿足題目要求。

---

python

問題分析

題目要求根據后序和中序遍歷結果構建二叉樹，并輸出層次遍歷結果。關鍵在于如何正確分割后序和中序序列以遞歸構建樹，并通過廣度優先遍歷（BFS）輸出層次遍歷結果。

---

解題思路

1. 構建二叉樹：
   • 后序的最后一個元素為當前子樹的根節點。
   • 在中序中找到根的位置，分割左、右子樹的中序序列。
   • 根據左子樹節點數，分割后序的左、右子樹部分。
   • 遞歸構建左子樹和右子樹。
2. 層次遍歷：使用隊列實現廣度優先遍歷（BFS），按層輸出節點。

---

代碼實現

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Nonefrom collections import dequedef build_tree(in_order, post_order):# 創建哈希表快速查找根節點在中序的位置hash_map = {val: idx for idx, val in enumerate(in_order)}def helper(in_left, in_right, post_left, post_right):if post_left > post_right:return None# 后序的最后一個元素是當前根節點root_val = post_order[post_right]root = TreeNode(root_val)# 查找根節點在中序中的位置root_idx = hash_map[root_val]# 左子樹的節點個數left_size = root_idx - in_left# 遞歸構建左子樹root.left = helper(in_left, root_idx - 1, post_left, post_left + left_size - 1)# 遞歸構建右子樹root.right = helper(root_idx + 1, in_right, post_left + left_size, post_right -