data-structures - 二叉树的连接

Question

假设我们有一组二叉树，其中给定了它们的中序和先序遍历，并且没有树是给定集合中另一棵树的子树。现在给定另一棵二叉树Q，求是否可以将给定集合中的二叉树连接起来形成。(同时连接集合中的每棵树应该被认为至多一次)连接操作的意思是:

选取集合中任意一棵树的根并将其连接到另一棵树的任意顶点，使得生成的树也是一棵二叉树。

我们可以使用 LCA(最不常见的祖先)来解决这个问题吗？还是需要任何特殊的数据结构来解决？

Answer 1

我认为二叉树结构应该足够了。我认为您不需要任何其他特殊的数据结构。

而且我不明白您将如何为此使用 LCA。据我所知，LCA 用于了解同一棵树中两个节点的最低公共(public)祖先。比较两棵树无济于事。 (这是我要检查是否可以形成 Q 的方法)

我的解决方案。

如果可以从树的集合中生成树 Q，则必须对其进行检查，因此我将采用自上而下的方法。基本上将 Q 与从集合中形成的可能树进行比较。

逻辑:如果 Q.root 与集合 (A,B,C....Z...) 中的任何树的根都不匹配，则无解。

如果 Q.root 匹配一个树根(比如 A)，检查相应的子节点并将 A 标记为已使用/已访问。 (这是我从问题中理解的:一棵树只能使用一次)

只有当 Q 的所有子级都与 A 的相应子级匹配时，我们才应该在我们的解决方案中继续使用 A。(我会进行深度优先遍历，广度优先也可以)。

我们可以从集合中追加一棵新树(即仅在 A 的叶节点追加一个新根(树 B)，因为我们必须维护二叉树)。跟踪 B 的附加位置。

与对 A 所做的相应子项比较重复相同的检查。如果没有匹配，则删除 B 并尝试在添加 B 的位置添加 C 树。

我们继续这样做，直到我们用完 Q 中的节点。(除非我们想要相同的匹配，在这种情况下，我们会尝试其他树组合，而不是我们拥有的树组合，它们匹配 Q 但有更多节点)。

对于冗长冗长的回答，我们深表歉意。 (我觉得我的伪代码会很难写，并且充满注释来解释)。

希望这对您有所帮助。

另一种解决方案:效率会低得多(仅当树的数量相对较少时才尝试):形成所有可能的树集(首先在 2s 然后 3s ....N)和检查形成的树是否它们与 Q 相同。比较部分可以引用这里: http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/