# 输出二叉树后序遍历结果

2026 华为OD机试真题 5月17日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定二叉树前序遍历和中序遍历的字符串，以及需要删除的节点，要求先解析这两个字符串获取对应二叉树，再做删除指定节点操作，然后输出该二叉树的后序遍历结果。删除节点规则：

1、指定节点是根节点，则不做删除操作；

2、指定节点是叶子节点，则直接删除；

3、指定节点是内部节点：

（1）如果是左子节点，则把该节点的左子树挂接到它的父节点，然后删除该节点以及它的右子树；

（2）如果是右子节点，则把该节点的右子树挂接到它的父节点，然后删除该节点以及它的左子树。

2026 华为OD机试真题 5月17日华为OD上机新系统考试真题 100 分题型

输入描述

string preorderStr // 前序遍历字符串

string inorderStr // 中序遍历字符串

char beDeletedNode // 待删除的节点

输出描述

string outputStr // 返回 "" 或者 后序遍历的字符串

string inorderStr // 中序遍历字符串

char beDeletedNode // 待删除的节点

注：

1、给定的preorderStr 和 inorderStr 是由大写字母组成的字符串，长度为2 \~ 26，每个字母表示一个节点值，且节点值唯一；

2、给定的 beDeletedLeafNode 是一个大写字母，如果输入的不是大写字母、或者找不到对应节点、或者找到的节点是根节点，都不做删除操作；

3、如果做了删除操作，则输出删除叶子节点后的二叉树后序遍历结果，否则直接输出二叉树后序遍历结果；

4、preorderStr 和 inorderStr 符合如下场景则输出空串""，例如：

（1）字符串中存在非大写字母；

（2）长度超出范围；

（3）节点值不唯一；

（4）两个字符串长度不一致；

（5）两个字符串元素不相同；

（6）无法解析出对应二叉树。

补充说明

1、程序运行内存要小于256MB；

2、程序运行耗时不能超过1秒。

示例1

输入

"23a","ABC",A

输出

""

说明

输入存在非法字符串

示例2

输入

"ADE","DAE",E

输出

"DA"

说明

示例3

输入

"AABCD","BAACD",A

输出

""

说明

出现重复节点值

示例4

输入

"ABC","BAC",A

输出

"BCA"

说明

找到的节点 A 是根节点

示例5

输入

"ABCDE","BAHDE",E

输出

""

说明

输入的两个遍历结果元素不相同

解题思路

核心思想

本题分为三个阶段：二叉树重建 → 节点删除 → 后序遍历。

阶段一：二叉树重建（递归）

• 前序遍历的第一个字符是根节点。
• 在中序遍历中定位根节点，左侧为左子树，右侧为右子树。
• 递归构造左右子树，返回根节点。
• 时间复杂度 O(n)，空间复杂度 O(n)。

阶段二：节点删除

• 根节点不删除。
• 叶子节点：直接断开父节点对应指针。
• 内部节点：
  • 左子节点：将目标节点的左子树接到父节点的左侧，然后断开目标节点及其右子树。
  • 右子节点：将目标节点的右子树接到父节点的右侧，然后断开目标节点及其左子树。
• 使用栈实现 DFS，找到目标节点的父节点。

阶段三：后序遍历

• 按 左子树 → 右子树 → 根节点 的顺序递归遍历。
• 输出为字符串。

复杂度分析

• 时间复杂度: O(n)，每个节点访问常数次。
• 空间复杂度: O(n)，递归栈 + 辅