21.华为OD机试：二叉树中序遍历解析 Java实现

📋 题目概述

题目来源

2023年华为OD统一考试B卷机考题

题目描述

根据给定的二叉树结构描述字符串，输出该二叉树的中序遍历结果字符串。二叉树节点数最大不超过100。

中序遍历顺序：左子树 → 根节点 → 右子树

输入描述

• 输入为由大小写字母、左右大括号、逗号组成的字符串

• 字母代表一个节点值

• 左右括号内包含该节点的子节点

• 左右子节点使用逗号分隔：

  • 逗号前为空表示左子节点为空

  • 没有逗号则表示右子节点为空

• 输入字符串格式保证正确，无需考虑格式错误

输出描述

输出一个字符串，为二叉树中序遍历各节点值的拼接结果

示例

输入：

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

输出：

dbgehIafc

🔍 题目解析

1. 字符串格式理解

题目中的字符串是一种特殊的二叉树表示法，类似于括号表示法：

• a{b,c} 表示节点a有左子节点b和右子节点c

• a{b,} 表示节点a有左子节点b，右子节点为空

• a{,c} 表示节点a左子节点为空，有右子节点c

• a{b} 表示节点a只有左子节点b（没有逗号）

2. 示例解析

对于示例输入 a{b{d,e{g,h{,I}}},c{f}}：

• 根节点：a

• 左子树：b{d,e{g,h{,I}}}

  • b的左子节点：d

  • b的右子节点：e{g,h{,I}}

• 右子树：c{f}

  • c的左子节点：f

  • c的右子节点：空

3. 解题思路

解决本题需要两个关键步骤：

1. 解析字符串，构建二叉树：将输入字符串转换为二叉树数据结构

2. 中序遍历二叉树：按照左-根-右的顺序遍历并拼接节点值

💡 算法设计

算法流程图

flowchart TD A[开始：输入字符串] --> B[解析字符串构建二叉树] B --> C[中序遍历二叉树] C --> D[拼接遍历结果] D --> E[输出结果字符串] subgraph B[解析字符串] B1[创建根节点] --> B2[解析左右子树] B2 --> B3[递归构建子树] end subgraph C[中序遍历] C1[访问左子树] --> C2[访问根节点] C2 --> C3[访问右子树] end

核心步骤详解

1. 字符串解析策略

• 使用递归下降法解析字符串

• 遇到字母：创建节点

• 遇到{：开始解析子节点

• 遇到,：分隔左右子节点

• 遇到}：结束当前子树解析

2. 中序遍历实现

• 递归实现：inorder(node.left) → visit(node) → inorder(node.right)

• 迭代实现：使用栈模拟递归过程