找到共同的祖先中的二进制树 [英] Finding the common ancestor in a binary tree

问题描述

这个问题是问我在接受采访时：我有一个二叉树，我必须找到考虑到树的两个随机节点的共同祖先（父）。我还给出一个指向根节点

This question was asked to me in an interview: I have a binary tree and I have to find the common ancestor (parent) given two random nodes of that tree. I am also given a pointer to the root node.

我的回答是：

分别遍历树的两个节点，直到你达到了预期的节点。 平行在遍历存储元件与下一个地址中一个链表。然后，我们有我们两个人链表。因此，尝试比较这两个链接列表，并在这两个链接列表的最后一个公共节点父。

Traverse the tree separately for both the nodes till you reach the node that is expected. Parallel while traversing store the element and the next address in a linked list. Then we have two linked lists with us. So try comparing the two linked lists and the last common node in both the linked lists is the parent.

我在想，这个解决方案是正确的，纠正我，如果我错了。 如果此解决方案是正确的，我知道这是这个任务的唯一较好的解决方案或有任何比这其他更好的解决方案！

I am thinking that this solution is correct, correct me if I am wrong. If this solution is correct, may I know is this the only better solution for this task or is there any other better solution than this!

推荐答案

也许傻的办法：

生成从每个节点到根的路径，将其存储为L和R的字符串。

Generate the path from each node to the root, storing it as a string of "L" and "R".

扭转这些字符串。就拿最长的共同preFIX - 你现在有路径的共同祖先

Reverse these strings. Take the longest common prefix - you now have the path to the common ancestor.

这篇关于找到共同的祖先中的二进制树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！