gpt4 book ai didi

data-structures - 二叉树的连接

转载 作者:行者123 更新时间:2023-12-02 03:16:39 25 4
gpt4 key购买 nike

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

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

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

最佳答案

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

而且我不明白您将如何为此使用 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/

关于data-structures - 二叉树的连接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36649448/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com