如何检测二叉树数组中是否存在共享指针节点的两棵树

你的原始思路是遍历所有树并存储所有节点指针后查重，这种方法的问题在于必须遍历完所有节点才能判断，且空间开销等于所有节点的总数，效率确实不高。以下是几种更高效的解决方案：

1. 哈希表实时查重（推荐） #

不用先存储所有节点，而是边遍历边检查：

• 初始化一个全局哈希表（或集合），用于记录已访问过的节点指针。
• 逐个遍历数组中的每棵树：
  • 对当前树进行深度优先遍历（DFS）或广度优先遍历（BFS），每访问一个节点，先检查它是否在哈希表中：
    • 如果存在，说明该节点被之前的树共享，直接返回true；
    • 如果不存在，将该节点指针存入哈希表。
• 若所有树遍历完成都未找到共享节点，返回false。

这种方法的优势在于可以提前终止——一旦找到共享节点就立刻停止遍历，无需处理剩余节点，平均时间复杂度远低于全量遍历。哈希表的插入和查找操作平均时间复杂度为O(1)，整体时间复杂度为O(M)（M是所有节点中到第一个共享节点为止的数量），空间复杂度为O(M)。

2. 节点标记法（低空间开销） #

如果允许对节点结构做临时修改，或者有语言特性支持，可以用标记法避免哈希表的空间开销：

侵入式标记（需修改节点） #

• 在二叉树节点结构中新增一个visited布尔字段（如果权限允许）。
• 遍历每棵树时，对每个节点进行检查：
  • 若visited为true，说明该节点被之前的树访问过，直接返回true；
  • 若visited为false，将其设为true。
• 若需要保留原树的状态，遍历完每棵树后要把所有节点的visited字段重置为false（如果还没找到共享节点的话）。

这种方法的空间复杂度为O(1)（仅需遍历的栈/队列空间），时间复杂度同样支持提前终止。

非侵入式时间戳标记（无需修改节点） #

如果不能修改节点结构，可以用时间戳替代布尔标记：

• 维护一个全局递增的时间戳变量，以及一个哈希表（键为节点指针，值为访问时间戳）。
• 遍历每棵树前，先将时间戳加1。
• 遍历当前树的节点时，检查哈希表中该节点对应的时间戳：
  • 若等于当前时间戳，说明该节点在本次遍历中被重复访问（树自身有环，不过题目是跨树共享，可忽略或单独处理）；
  • 若等于之前的时间戳，说明该节点被其他树访问过，返回true；
  • 若不存在，将该节点和当前时间戳存入哈希表。

这种方法无需修改节点的持久化状态，空间开销仅为哈希表存储已访问节点的开销，同样支持提前终止。

3. 小树优先遍历优化 #

针对哈希表实时查重的方法，可以进一步优化遍历顺序：

• 先遍历数组中节点数量最少的树，将其所有节点存入哈希表。
• 再依次遍历其他树，每访问一个节点就检查哈希表，一旦找到匹配就返回true。

这种优化的逻辑是：共享节点更大概率存在于节点数少的树中，提前遍历小树可以更快完成哈希表的构建，后续遍历大树时能更早触发匹配。

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