gpt4 book ai didi

c - 在二叉树中寻找共同祖先

转载 作者:太空狗 更新时间:2023-10-29 17:05:36 24 4
gpt4 key购买 nike

我在一次采访中被问到这个问题:我有一个二叉树,我必须找到给定该树的两个随机节点的共同祖先(父节点)。我还获得了指向根节点的指针。


我的答案是:

分别为两个节点遍历树,直到到达预期的节点。并行遍历将元素和下一个地址存储在链表中。然后我们有两个链表。所以尝试比较两个链表,两个链表中的最后一个公共(public)节点是父节点。

我认为这个解决方案是正确的,如果我错了请纠正我。如果这个解决方案是正确的,请问这是完成这项任务的唯一更好的解决方案,还是有比这更好的解决方案!

最佳答案

也许是愚蠢的做法:

生成每个节点到根的路径,存储为“L”和“R”的字符串。

反转这些字符串。取最长的公共(public)前缀 - 你现在有通往共同祖先的路径。

关于c - 在二叉树中寻找共同祖先,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6175020/

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