同一子树的二叉树压缩

Question

给定一棵树，找到公共子树并替换公共子树并压缩树。例如

应转换为

      1
     /  \
     2   3
   / |   /\
  4  5   | |

  ^  ^   | |

  |__|___| |

     |_____|

这是在我的采访中被问到的。我分享的方法不是最佳的 O(n^2)，如果有人可以帮助解决或将我重定向到类似的问题，我将不胜感激。我找不到任何。然后！

编辑-更复杂，例如：

应替换以 2 为根的整个子树。

      1
     /  \
     2 <--3
   / |     \
  4  5      7

Answer 1

您可以使用来自 (value, left_pointer, right_pointer) -> node 的散列映射在单个 DFS 遍历中执行此操作，以折叠重复出现的子树。

当您将每个节点留在 DFS 中时，您只需在地图中查找即可。如果匹配的节点已经存在，则将其替换为 pre-existing 节点。否则，将其添加到地图中。

这需要O(n)的时间，因为你是在比较实际的指针指向左+右子树，而不是遍历树来比较它们。指针比较结果相同，因为左右子树已经规范化.

Answer 2

首先，我们需要存储出现在散列中的节点值table。如果树已经存在，我们可以迭代树，如果节点值已经在节点集中，则删除该节点的分支。否则，将值存储在哈希映射中，每次创建新节点时，检查该值是否出现在映射中。

binary tree compaction of same subtree