xxx 树同构问题的 AHU 算法 题目描述 给定两棵有根树（每个树有 n 个结点，结点编号为 1 到 n）。要求判断这两棵树是否同构。两棵树同构，意味着可以通过重命名结点（即建立一个结点间的一一映射），使得两棵树的结构完全相同（父子关系一致）。AHU 算法（由 Alfred V. Aho、John E. Hopcroft 和 Jeffrey D. Ullman 提出）通过为树的每个结点计算一个唯一的“规范编码”（canonical form），来高效判定有根树是否同构。 解题过程循序渐进讲解 第一步：理解有根树同构的定义 对于两棵有根树 T1 和 T2，如果存在一个双射函数 f: V(T1) → V(T2)，使得对于 T1 中的任意结点 u 和它的子结点 v，f(v) 是 f(u) 在 T2 中的子结点，则 T1 和 T2 同构。 简单说：可以给两棵树的结点重新标号，使得它们的层次结构（父子、兄弟顺序可交换）完全一样。 注意：AHU 算法通常处理 无序树 ，即子结点之间没有顺序关系，交换子结点不改变树的结构。 第二步：算法核心思想 AHU 算法采用 自底向上 的方式，为每个结点生成一个唯一的“编码字符串”。 叶结点的编码是固定的（例如 "()" 或 "01" 等，只要一致即可）。 对于非叶结点，先递归计算出其所有子结点的编码，将这些编码 按字典序排序 ，再拼接起来并用括号包裹，形成该结点的编码。 两棵树同构，当且仅当它们根结点的编码字符串完全相同。 为什么排序？因为子结点是无序的，排序后可以消除兄弟顺序的影响，使得同构的树必然得到相同编码。 第三步：详细步骤与示例 假设我们用括号表示法，叶结点编码为 "()"。 例：比较两棵有根树（根均为 1） 树 A: 1→[ 2,3], 2→[ 4], 3→[], 4→[ ] 树 B: 1→[ 2,3], 2→[], 3→[ 4], 4→[ ] （两棵树实际上是同构的，可以通过交换结点 2 和 3 及它们的子树得到相同结构） 步骤 1：从叶结点开始计算编码 叶结点（如 3,4 在 A 中）：编码为 "()"。 步骤 2：向上传递 对结点 2（在 A 中），子结点是 4（叶结点），子结点编码列表为 [ "()"]，排序后仍为 [ "()" ]，拼接并加括号得到 "(())"。 对结点 3（在 A 中），无子结点，编码为 "()"。 步骤 3：根结点 1 子结点是 2 和 3，编码列表为 [ "(())", "()"]，按字典序排序为 [ "()", "(())"]（因为 "()" < "(())"），拼接得到 "()(())"，再加括号得 "(()(()))"。 同理，计算树 B 的根结点编码，也会得到完全相同的 "(()(()))"，因此两棵树同构。 第四步：算法实现细节 树的存储：用邻接表，并指定根。 递归函数 compute_ code(u): 如果 u 是叶结点：返回 "()"。 否则，递归计算 u 的所有子结点的编码，存入列表 child_ codes。 对 child_ codes 进行字典序排序。 将排序后的字符串按顺序拼接，并在最外层加上括号，返回。 比较两棵树根结点的编码字符串是否相等。 第五步：复杂度与优化 时间复杂度 O(n log n)：每个结点处对子结点编码排序，总排序代价可摊到 O(n log n)（若用比较排序）。 空间复杂度 O(n)：存储编码字符串，每个结点编码长度可达到 O(n)，但总字符数 O(n²) 在实践中可通过哈希优化（见下一步）。 第六步：哈希优化（树哈希） 为了不直接比较长字符串，可以用哈希值代替： 叶结点哈希设为常数（如 1）。 对子结点哈希列表排序后，通过一个哈希函数（例如多项式哈希）将序列映射为一个整数，作为当前结点的哈希。 比较两棵树根结点的哈希值是否相等（冲突概率极小）。 这样时间 O(n log n)，空间 O(n)，且避免了字符串操作。 第七步：无根树同构的处理 对于无根树，可选树的重心（最多两个）作为根，分别计算编码，只要有一个根的编码与另一棵树的某个根的编码相同，则两棵树同构。因为重心个数 ≤2，所以只需常数次比较。 总结 AHU 算法通过自底向上的规范编码，将有根树同构判定转化为字符串/哈希值比较，清晰高效，是无序树同构判定的经典算法。