二叉树重复子树检测算法的时间与空间复杂度存疑

你的分析在朴素字符串序列化实现的场景下完全正确，而资料中提到的O(N)时间/空间复杂度，是基于优化后的序列化方案，两者的前提不同，具体拆解如下：

• 朴素字符串序列化的问题（O(N²)复杂度）
  当采用直接拼接字符串的方式序列化子树时：

  • 空间上：最坏情况比如链式二叉树（每个节点仅左孩子），每个子树的序列化字符串长度等于子树节点数，总共有N个子树，总字符量为1+2+...+N = O(N²)，因此哈希集合的空间开销是O(N²)。
  • 时间上：每次字符串拼接操作的时间与字符串长度正相关，每个字符会被多次复制，总时间复杂度同样是O(N²)。
    你提到用std::vector<char>实现O(1)拼接，本质是避免了字符串复制的开销，但总存储的字符总量仍为O(N²)，空间复杂度并没有降低。

• 优化方案下的O(N)复杂度
  资料中说的O(N)是基于以下优化手段：

  • 子树哈希值替代完整字符串：后序遍历过程中，直接计算每个子树的哈希值（例如将左子树哈希、节点值、右子树哈希通过某种哈希函数组合），将哈希值存入集合而非完整字符串。每个节点的哈希计算是O(1)操作，总时间O(N)，集合中仅存储N个哈希值（如整数），空间O(N)。
  • 唯一ID映射：维护一个哈希表，将每个唯一的子树结构映射到一个唯一ID。遍历过程中，若子树结构已存在则复用ID，否则生成新ID。这种方式仅需存储ID和映射关系，空间和时间均为O(N)。

简单来说，朴素实现确实是O(N²)，而资料中的O(N)是针对优化后的高效实现而言，二者的差异在于是否用紧凑的标识（哈希值/ID）替代了完整的子树序列化字符串。

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