华为OD机试真题——二叉树中序遍历（2025A卷：200分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025 A卷 200分 题型

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

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《二叉树中序遍历》：

---

---

题目名称：二叉树中序遍历

---

• 知识点：字符串解析、栈操作（递归）
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

输入一个由字母、大括号和逗号组成的字符串表示二叉树结构：

• 单个字母表示节点值，大括号内为子节点，逗号分隔左、右子节点。逗号前为空则左子节点为空，无逗号则右子节点为空。
• 例如，输入 a{b{c},d{e,f}} 表示根节点为 a，左子节点为 b{c}（b 有左子节点 c），右子节点为 d{e,f}（d 有左子节点 e，右子节点 f）。

输入描述
一行字符串，表示二叉树结构，如 a{b{d,e{g,h{,i}}},c{f}}。

输出描述
输出中序遍历结果的拼接字符串，如 dbgehiafc。

示例

输入：

a{b{d,e{g,h{,i}}},c{f}}  

输出：

dbgehiafc  

补充说明

• 节点数不超过 100。
• 输入字符串格式正确，无需校验。

---

Java

题目分析

我们需要将特定格式的字符串转换为二叉树结构，并进行中序遍历。字符串格式为：每个节点由字母表示，子节点用大括号包裹，逗号分隔左右子节点。例如，a{b{c},d{e,f}} 表示根节点 a 有左子节点 b（其左子节点为 c）和右子节点 d（其左右子节点为 e 和 f）。

---

解决思路

1. 字符串解析：使用递归和栈的思想处理嵌套结构，分割左右子节点。
2. 树构建：递归解析每个节点及其子节点，构建二叉树。
3. 中序遍历：递归遍历二叉树，拼接结果。

---

Java 代码实现

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 input = scanner.nextLine().trim();TreeNode root = parse(input);String result = inorder(root);System.out.println(result);}// 解析字符串为二叉树private static TreeNode parse(String s) {if (s.isEmpty()) return null;int i = 0;// 提取当前节点值（第一个字母）char val = s.charAt(i++);TreeNode node = new TreeNode(val);// 检查是否有子节点（是否有 '{'）if (i < s.length() && s.charAt(i) == '{') {int start = i;int count = 1; // 括号层数计数器i++; // 跳过 '{'// 找到匹配的 '}'while (i < s.length() && count > 0) {if (s.charAt(i) == '{') count++;else if (s.charAt(i) == '}') count--;i++;}// 子节点部分（去掉外层括号）String children = s.substring(start + 1, i - 1);// 分割左右子节点List<String> parts = splitChildren(children);node.left = parse(parts.get(0));node.right = parse(parts.get(1));}return node;}// 分割左右子节点字符串private static List<String> splitChildren(String s) {List<String> parts = new ArrayList<>();int count = 0; // 括号层数int splitIndex = -1;// 遍历找到第一个外层逗号for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '{') count++;else if (c == '}') count--;else if (c == ',' && count == 0) {splitIndex = i;break;}}if (splitIndex != -1) { // 存在分割点parts.add(s.substring(0, splitIndex));parts.add(s.substring(splitIndex + 1));} else { // 无分割点，整个字符串是左子节点parts.add(s);parts.add("");}return parts;}// 中序遍历二叉树private static String inorder(TreeNode root) {if (root == null) return "";return inorder(root.left) + root.val + inorder(root.right);}
}

---

代码详细解析

1. TreeNode 类：定义二叉树的节点结构，包含值和左右子节点。
2. parse 方法：
   • 提取节点值，处理子节点部分。
   • 使用括号层数计数器匹配 {}，截取子节点字符串。
   • 递归解析左右子节点。
3. splitChildren 方法：
   • 遍历子节点字符串，找到第一个外层逗号分割左右子节点。
   • 处理嵌套括号，确保分割正确。
4. inorder 方法：递归中序遍历，拼接结果字符串。

---

示例测试

示例1：
输入：a{b{d,e{g,h{,i}}},c{f}}
输出：dbgehiafc
解析过程：

• 根节点 a，左子节点 b 和右子节点 c。
• b 的左子节点 d，右子节点 e。e 的左子节点 g，右子节点 h。
• h 的右子节点 i，c 的左子节点 f。
• 中序遍历顺序：d -> b -> g -> e -> h -> i -> a -> f -> c。

示例2：
输入：x{y{z},w}
输出：zyxw
解析过程：

• 根节点 x，左子节点 y 和右子节点 w。
• y 的左子节点 z。
• 中序遍历顺序：z -> y -> x -> w。

---

综合分析

1. 高效性：递归解析字符串，时间复杂度 O(n)。
2. 健壮性：处理嵌套括号和逗号分割，确保正确分割子节点。
3. 简洁性：利用递归和字符串操作，代码逻辑清晰。
4. 适用性：完全符合题目要求，处理各种边界条件。

---

python

题目分析

我们需要将特定格式的字符串转换为二叉树结构，并进行中序遍历。字符串格式规则为：单个字母表示节点值，大括号内为子节点，逗号分隔左、右子节点。例如，a{b{c},d{e,f}} 表示根节点 a 的左子节点为 b（其左子节点为 c），右子节点为 d（其左右子节点为 e 和 f）。

---

解决思路

1. 字符串解析：递归解析字符串，处理嵌套的大括号结构，分割左右子节点。
2. 树构建：根据解析结果递归构建二叉树。
3. 中序遍历：递归遍历二叉树，拼接结果字符串。

---

Python 代码实现

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Nonedef parse(s):"""解析字符串为二叉树:param s: 当前处理的子字符串（如 "a{b{c},d{e,f}}"）:return: 当前子树的根节点"""if not s:return None# 提取当前节点值（第一个字符）val = s[0]node = TreeNode(val)idx = 1  # 当前处理位置的索引# 检查是否有子节点（是否有 '{'）if idx < len(s) and s[idx] == '{':idx += 1  # 跳过 '{'start = idxcount = 1  # 括号层数计数器# 找到匹配的 '}'while idx < len(s) and count > 0:if s[idx] == '{':count += 1elif s[idx] == '}':count -= 1idx += 1# 提取子节点部分（去掉外层 '{}'）children_str = s[start: idx-1]# 分割左右子节点字符串left_str, right_str = split_children(children_str)# 递归处理左子树和右子树node.left = parse(left_str)node.right = parse(right_str)return nodedef split_children(s):"""分割左右子节点字符串（处理嵌套括号）:param s: 子节点部分的字符串（如 "b{c},d{e,f}"）:return: (左子节点字符串, 右子节点字符串)"""count = 0  # 括号层数split_idx = -1# 遍历寻找最外层的逗号for i, c in enumerate(s):if c == '{':count += 1elif c == '}':count -= 1elif c == ',' and count == 0:split_idx = ibreak  # 找到第一个可分割的逗号if split_idx != -1:# 分割左、右子节点部分return s[:split_idx], s[split_idx+1:]else:# 无逗号表示只有左子树，右子树为空return s, ''def inorder(root):"""中序遍历二叉树，拼接结果字符串:param root: 当前节点:return: 遍历结果字符串"""if not root:return ''return inorder(root.left) + root.val + inorder(root.right)# 输入处理
input_str = input().strip()
root = parse(input_str)
print(inorder(root))

---

代码详细解析

1. TreeNode 类

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = None

• 定义二叉树节点结构，包含值和左右子节点。

2. parse 函数

def parse(s):if not s:return Noneval