我们如何确定给定树 T 是否包含与另一棵树 S 同构的子树？
如果其中一棵树可以通过一系列翻转从另一棵树中获得，则称两棵树是同构的，即通过交换多个节点的左右子节点。任何级别的任何数量的节点都可以交换它们的子节点。两棵空树是同构的。
我在一些地方读到过可以使用二分匹配算法来解决这个问题，但是我找不到任何非付费资源来了解详细信息。似乎有很多关于这个问题的研究论文，其中大部分都再次落后于付费专区，但是我目前对这个问题的最新研究算法不感兴趣。我的问题是二分匹配如何应用于这个问题？
PS:网上似乎对“同构”的含义有些混淆。以上是我在大多数地方找到的定义，但有些地方提到“同构”意味着无论节点值如何，树都具有相同的形状。如果有人能消除这种困惑，那也太好了。
最佳答案
我要讲的是有根子树同构；通过尝试所有根，可以在不考虑效率的情况下处理无根情况。
基本思想是如果你有树
A B
/|\ /|\
/ | \ / | \
/ | \ / | \
a1 ... am b1 ... bn
/\ /\ /\ /\
并想知道 A 是否是 B 的子树，使得 A 映射到 B，然后对于所有 i 和 j，您递归地计算以 ai 为根的子树是否是以 为根的树的子树bj 以 ai 映射到 bj 的方式。 (基本情况是 A 或 B 是叶子。)现在，每个子树都可映射是不够的，因为如果某些 bj有一个特别丰富的结构，那么几个ai可能是子树，但是同构的要求不会让它们共享那个bj。这就是最大匹配的用武之地:我们尝试以可以映射子树的方式将所有 ai 与 bj 匹配。
要解决一般的有根问题，请尝试所有可能的 B 选项。
关于algorithm - 如何使用最大二分匹配解决子树同构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29873740/