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

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

题目描述

业务数据处理中经常使用二叉树来表示数据结构 ，为了存储时尽可能的减少空间占用，需要找出树中重复的子树。给出定义的一颗二叉树，按照要求输出该二叉树中所有的重复子树，对于用一类 重复的子树只需要返回其中一个结果即可：

输入：二叉树的节点

输出：重复子树构成的字符串数组（重复子树的序列化规则：按照前序遍历输出，空节点用'＃'表示，节点值直接输出，用逗号分隔，例如叶子结点2的序列化为"2,#,#"；字符串数组的输出顺序为：序列化后节点多的子树在数组前面，如果节点数一样，则根据子树遍历前序顺序输出）注意：没有找到重复子树则输出空数组。 补充说明：

1. 如果两棵树具有相同的结构和相同的结点值，则认为二者是重复的；
2. 输入示例是二叉树的层序遍历，空节点用"#"表示

输入描述

指定二叉树层序遍历结果，多个节点之间使用,进行分割。其中#代表空节点。

输出描述

按要求输出所有重复子树序列化结构，多个子树的序列化结果之间优先按照节点数进行降序，节点数相同的根据子树遍历前序顺序升序。多个序列化结果之间使用换行输出。

示例1

输入

1,2,3,4,#,2,4,#,#,4

输出

2,4,#,#,#
4,#,#

说明

示例2

输入

5,7,7

输出

7,#,#

说明

解题思路

核心思想

本题要求找出二叉树中所有重复的子树，并按照特定规则输出。核心思路是通过序列化将子树唯一表示，然后统计出现次数。

具体步骤如下：

1. 子树序列化：对每个子树进行前序遍历序列化，空节点用 # 表示。例如叶子节点 2 序列化后为 "2,#,#"。

2. DFS遍历：使用深度优先搜索遍历整棵树，对每个节点进行序列化，并统计每种序列化结果出现的次数。

3. 重复检测：当某个序列化结果出现第二次时，说明找到了重复子树，记录该子树的信息（节点数、前序顺序、序列化字符串）。

4. 结果排序：将所有重复子树按以下规则排序：

   • 节点数降序（节点多的在前）
   • 前序顺序升序（遍历顺序靠前的在前）

5. 输出：按排序后的顺序输出所有重复子树的序列化结果。

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点只访问一次。
• 空间复杂度：$O(N)$，需要存储所有子树的序列化结果和相关信息。