加入二叉树

Question

假设我们有一组二叉树，其中有序和前序遍历，并且没有树是给定集合中另一棵树的子树。现在给出另一个二叉树Q，找出它是否可以通过加入给定集合中的二叉树来形成（同时加入集合中的每棵树应该被认为是最后一次）加入操作意味着：

选择集合中的任何树并将其挂接到另一棵树的任何顶点，使得生成的树也是二叉树。

我们可以使用LCA（最小共同祖先）来做到这一点吗？还是需要任何特殊的数据结构来解决？

Answer 1

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

我不明白你会如何使用生命周期评估。据我所知，LCA用于了解同一棵树中两个NODES的最低公共祖先。它不会帮助比较两棵树。 （这是我会做什么来检查是否可以形成Q）

我的解决方案是文字。

树Q必须检查，如果它可以从一组树，所以我会采取自上而下的方法。基本上将Q与由该集合形成的可能的树相比较。

逻辑： 如果Q.root与集合（A，B，C .... Z ...）中的任何树根都不匹配，则无法解决问题。

如果Q.root匹配树根（比如A），检查相应的子项并将A标记为used/visited。 （这是我从这个问题中了解到的：一棵树只能使用一次）

只有当所有Q的子元素都与A的相应子元素相匹配时，我们才应该继续使用A（我会做深度优先遍历，广度优先也可以）。

我们可以从集合中追加一棵新的树（即仅在A的叶节点追加新的根（树B），就像我们必须维护二叉树一样）。跟踪B的附加位置。

重复与相应的儿童比较相同的检查，如A所做。如果不匹配，请删除B并尝试在添加了B的地方添加C树。 （除非我们想要IDENTICAL MATCH，在这种情况下，我们会尝试其他的树组合，而不是我们拥有的树组合，它们与Q匹配，但有更多的节点） 。

道歉为冗长冗长的答案。 （我觉得我的伪代码很难编写，并且有很多解释的评论）。

希望这会有所帮助。

另一种解决方案：效率会低得多（只在树数相对较少的情况下尝试）：形成所有可能的树集合（首先是2s然后3s ... N）并且检查已形成的树如果他们是相同的Q. 比较部件可以在这里简称： http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/