同构树顶点匹配问题：寻求O(N)/O(NlogN)复杂度的解决方案

核心思路：基于树哈希的分层匹配 #

从叶子节点开始向上计算每个节点的特征哈希，通过哈希值区分同度节点，再用BFS/DFS完成匹配，复杂度可做到O(N)或O(NlogN)。

• 步骤1：预处理叶子节点，计算初始哈希
  先遍历两棵树，标记所有叶子节点（度为1的节点；若为无根树，先选一个特征唯一的节点当根，比如哈希值最大的；若为有根树直接用给定根）。给所有叶子节点分配初始哈希值（比如统一设为0）。

• 步骤2：自底向上计算节点哈希
  用递归或队列处理节点，当一个节点的所有子节点（除父节点外）都已计算哈希时，将子节点的哈希值排序后拼接（或用哈希函数合并），作为当前节点的哈希值。示例代码（Python）：

  def compute_hash(node, parent, tree, hash_map, processed):
      children = [child for child in tree[node] if child != parent]
      if not children:
          hash_map[node] = 0
          processed.add(node)
          return
      child_hashes = []
      for child in children:
          if child not in processed:
              compute_hash(child, node, tree, hash_map, processed)
          child_hashes.append(hash_map[child])
      child_hashes.sort()
      # 直接用排序后的哈希元组作为当前节点的特征哈希
      hash_map[node] = tuple(child_hashes)
      processed.add(node)
  

  同构位置的节点会拥有相同的哈希值，哪怕度数相同，只要子树结构不同，哈希就会有差异，这是区分同度节点的关键。

• 步骤3：基于哈希的BFS匹配

  1. 初始匹配：在两棵树中找到一对哈希值相同的节点作为起点（比如选第一棵树节点0对应的第二棵树中哈希匹配的节点，或选哈希值唯一的节点）。
  2. 队列维护：用队列保存已匹配的节点对(u, v)，对于每个u的邻居u_nei，获取其哈希值h；在v的未匹配邻居中找到哈希值为h的v_nei，建立匹配关系u_nei → v_nei，将(u_nei, v_nei)加入队列。
  3. 重复操作直到所有节点完成匹配。

优势：解决同度节点匹配失效问题 #

单纯按最大度节点BFS的方案，会在多个节点度数相同且子树结构相似时无法区分，而树哈希是子树结构的抽象表达，能精准识别同构位置的节点，确保匹配的正确性。

复杂度分析 #

• 哈希计算：每个节点遍历一次子节点，排序子节点哈希的总时间为O(NlogD)（D为节点最大度数），树的平均度数为2，实际接近O(N)；最坏情况为O(NlogN)。
• BFS匹配：每个节点仅处理一次，时间复杂度O(N)。
• 整体复杂度满足题目要求的O(N)或O(NlogN)。

对称结构处理 #

若树存在对称结构（如完全二叉树），会出现多个节点哈希值相同的情况，此时任意选择符合哈希条件的节点匹配即可，符合题目"任意有效匹配均可"的要求。

内容的提问来源于stack exchange，提问作者Egor