我在一次采访中被问到这个问题:我有一个二叉树,我必须找到给定该树的两个随机节点的共同祖先(父节点)。我还获得了指向根节点的指针。
我的答案是:
分别为两个节点遍历树,直到到达预期的节点。 并行遍历将元素和下一个地址存储在链表中。然后我们有两个链表。所以尝试比较两个链表,两个链表中的最后一个公共(public)节点是父节点。
我认为这个解决方案是正确的,如果我错了请纠正我。 如果这个解决方案是正确的,请问这是完成这项任务的唯一更好的解决方案,还是有比这更好的解决方案!
最佳答案
也许是愚蠢的做法:
生成每个节点到根的路径,存储为“L”和“R”的字符串。
反转这些字符串。取最长的公共(public)前缀 - 你现在有通往共同祖先的路径。
关于c - 在二叉树中寻找共同祖先,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6175020/