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 -