在二叉树中查找共同的祖先
我在一次采访中向我询问了这个问题：我有一个二叉树，我必须找到该树的两个随机节点的共同祖先（父）。 我也得到了一个指向根节点的指针。
我的回答是：
分别遍历两个节点的树，直到到达预期的节点。 遍历时并行存储元素和链接列表中的下一个地址。 然后我们有两个链接列表。 因此，尝试比较两个链表，两个链表中的最后一个公共节点是父列表。
我认为这个解决方案是正确的，如果我错了，请纠正我。 如果这个解决方案是正确的，我可能知道这是这项任务的唯一更好的解决方案还是有比这更好的解决方案！
也许愚蠢的方法：
生成从每个节点到根的路径，将其存储为“L”和“R”字符串。
反转这些字符串。 采用最长的公共前缀 – 您现在拥有共同祖先的路径。
在两个随机节点上设置指针。 通过遍历顶部并计算距根节点的距离来查找每个节点的深度。 然后再次将指针设置在两个节点上。 对于更深的节点，遍历直到两个指针都处于相同的深度。 然后遍历两个节点，直到指针指向同一节点。 那是祖先节点。
通过“遍历”我只是意味着将指针移动到当前节点的父节点。
编辑以澄清：关键的想法是，当两个节点处于相同的深度时，您可以通过简单的遍历非常快地找到共同的父节点。 所以你爬下一个直到两个都在同一深度，然后你走了。 对不起，我真的不知道C或我写代码，但该算法应该回答你的问题。
再次编辑：我的方法在O（log（n））时间和O（1）内存中运行。
另一个编辑：平衡树中的O（log（n））。 对于不平衡树，最坏情况性能是O（n）。 谢谢@DaveCahill
我想你可以同时搜索两个节点; 搜索发散的点是共同的祖先。
commonAncestor tree ab: value := if (a < value) && (b < value) then commonAncestor (left tree) ab else if (a > value) && (b > value) then commonAncestor (right tree) ab else tree 有趣的是，这种方法可以扩展到两个以上的节点（检查所有节点是否在tree的左侧，等等）
进行级别订单遍历，对于我们遇到的每个节点，我们检查其子级。 如果它们是提供的随机节点，则找到祖先节点。
EDIT1：
这是一个大纲
struct _node { my_type data; struct _node *left; struct _node *right; } q = queue_create (); queue_insert (q, head); temp = head; while (!empty (q)) { temp = queue_remove (q); if ( (temp->left == my_random_node_1) && (head->right == my_random_node_2) || (temp->left == my_random_node_2) && (head->right == my_random_node_1) ) { /* temp is the common parent of the two target notes */ /* Do stuffs you need to do */ } /* Enqueue the childs, so that in successive iterations we can * check them, by taking out from the queue */ push (q, temp->left); push (q, temp->right); }
UPDATE
先前的算法将只找到共同的父母（直接祖先），因此如果两个随机选择的节点如果不是普通父母的孩子，则不会找到答案。
以下算法将找到共同的祖先，而不仅仅是父母。
我认为以下算法将起作用：
对二叉树进行后序遍历，找到随机节点1 r1 ，如果我们找到它然后将状态变量标记为状态1 ，并继续查找第二个节点，如果找到则更新状态变量说明两点 ，并停止搜索更多并返回。 状态变量应该由每个节点传递给它的父节点（递归地）。 在状态2中遇到状态变量的第一个节点是共同的祖先。
算法的实现如下：
int postorder (node *p, int r1, int r2) { int x = 0; /* The state variable */ if (p->data == TERMINAL_VAL) return x; /* 0x01 | 0x02 = 0x03 threfore * state one is when x = 0x01 or x = 0x02 * state two is when x = 0x03 */ if (p->data == r1) x |= 0x01; else if (p->data == r2) x |= 0x02; /* if we have x in state two, no need to search more */ if (x != 0x03) x |= postorder (p->left, r1, r2); if (x != 0x03) x |= postorder (p->right, r1, r2); /* In this node we are in state two, print node if this node * is not any of the two nodes r1 and r2. This makes sure that * is one random node is an ancestor of another random node * then it will not be printed instead its parent will be printed */ if ((x == 0x03) && (p->data != r1) && (p->data != r2)) { printf ("[%c] ", p->data); /* set state variable to 0 if we do not want to print * the ancestors of the first ancestor */ x = 0; } /* return state variable to parent */ return x; }
我认为这将正常工作，但我仍然要certificate算法的正确性。 有一个缺点，即如果一个节点是另一个节点的子节点，那么它将仅打印作为另一个节点的父节点的节点，而不是打印它们的父节点。 如果随机节点之一是另一个随机节点的祖先，则代替打印祖先随机节点，它将打印其父节点。 在其中一个随机节点是根节点的情况下，它将不打印任何内容，因为它始终是另一个随机节点的祖先，因此它们的共同祖先不存在。 在这种特殊情况下，函数将在main返回0x03 ，并且可以检测到它。
由于该算法执行后序遍历，因此它需要O（n）执行时间并因此需要O（n）存储器。 此外，一旦找到两个节点，搜索就会停止，节点越浅，搜索结束的速度越快。
UPDATE
以下是一些模式讨论： 如何在任何二叉树中找到两个节点的最低共同祖先？
这个问题已得到很好的研究，并且已知的算法可以在线性时间内解决它。 本文介绍了可用于解决此问题的许多不同方法。 不过，这是一篇研究论文，所以算法有点棘手，但它描述的一些方法实际上是非常可行的。
@Above，这不起作用，因为你假设两个节点都是某个特定节点的直接子节点…
8 10 12 7
我把节点分为7和12，答案必须是8.让我们这样做
find(root, d1, d2, n1=null, n2=null) { if(n1 && n2) return; if(!root) return; else if(root -> d == d1 ) n1 = root; else if(root -> d == d2 ) n2 = root; find(root->left, d1, d2, n1, n2); find(root->right, d1, d2, n1, n2); } LCA(root, d1, d2) { node *n1=null, *n2=null; find(root, d1, d2, n1, n2); if(n1 == null || n2 == null )error 'nodes not present' exit(0); findIntersect(n1, n2); } findInterSect(node *n1, node *n2) { l1 = length(n1); l2 = length(n2); node *g = n2, *l = n1; diff = abs(l1 - l2); if(l1>l2) g = n1 l =n2 while(diff) g = g->parent; diff--; // now both nodes are at same level while(g != l) g= g->parent, l = l->parent; }
伪代码：
node *FindCommonAncestor(node *root, node *node1, node *node2) { node *current = node1; node_list temp_list; temp_list.add(current); while (current != root) { current = current.parent; temp_list.add(current); } current = node2; while (current not in temp_list) { current = current.parent; } return current; }
如果节点肯定是同一棵树的一部分，那么它们肯定会有一个共同的祖先（即使它是最坏情况下的根）。 所以它总是会终止，并且没有错误的条件需要担心。
第一个循环运行n次，其中n是node1的深度，因此它是O（n）。 第二个循环运行m次，其中m在node2的深度。 查找临时列表是（最坏的）n。 所以第二个循环是O（m * n），它占主导地位，所以函数在O（m * n）中运行。
如果为临时空间而不是列表使用良好的设置数据结构（例如，哈希表），则可以将查找切换为（通常）O（1），而不会增加将节点添加到temp的成本。 这将我们的function时间减少到O（m）。
无论哪种方式，空间要求都是O（n）。
由于我们不提前知道n和m，所以让我们根据树中节点的总数来说：S。如果树是平衡的，那么n和m都是由log_2（S）限定的，所以运行时间为O（log_2（S）^ 2）。 Log_2非常强大，所以在我担心2的function之前，S必须变得非常大。如果树不平衡，那么我们就会丢失log_2（树可能实际上退化为链表）。 因此绝对最坏的情况（当一个节点是根节点而另一个节点是完全退化树的叶子时）是O（S ^ 2）。
嗨这将返回最低祖先节点值，其中树的根和val1，val2 – >节点的数据值正在传递
int CommonAncestor(node *root, int val1,int val2) { if(root == NULL || (! root->left && ! root->right ) return false; while(root) { if(root->data < val1 && root->data < val2) { root = root->left; } else if(root->data > val1 && root->data > val2) { root= root->right; } else return root->data; } }
-
预订遍历，除非满足任何1个节点并保存现在访问过的节点。
-
按顺序遍历，在满足任何1个（提供的两个节点中）节点时开始保存节点，并保存列表直到满足下一个节点。
- 发布订单遍历，当两个节点都被访问时开始保存节点…
一个
公元前
DEFG
HIJKLMNO
假设H和E是两个随机节点。
- ABDH
- HDIBJE
- EBLMENOGCA
找到这三个中常见的第一个节点……
以下是c＃（。net）中的两种方法（均在上面讨论过）供参考：
-
在二叉树中寻找LCA的递归版本（O（N） – 至多访问每个节点）（解决方案的主要观点是LCA是（a）二叉树中的唯一节点，其中两个元素都位于子树的任一侧（左侧） LCA。 （b）并且无论哪个节点出现在任何一方并不重要 – 最初我试图保留该信息，显然递归函数变得如此令人困惑。一旦我意识到它，它变得非常优雅。
-
搜索两个节点（O（N）），并跟踪路径（使用额外的空间 – 所以，＃1可能更好，即使二进制树很平衡，因为额外的内存消耗将只是在为O（log（N））。
以便比较路径（与接受的答案类似 – 但是通过假设二进制树节点中不存在指针节点来计算路径）
-
仅为完成（ 与问题无关 ），BST中的LCA（O（log（N））
-
测试
递归：
private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, int e1, int e2) { Debug.Assert(e1 != e2); if(treeNode == null) { return null; } if((treeNode.Element == e1) || (treeNode.Element == e2)) { //we don't care which element is present (e1 or e2), we just need to check //if one of them is there return treeNode; } var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2); var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2); if(nLeft != null && nRight != null) { //note that this condition will be true only at least common ancestor return treeNode; } else if(nLeft != null) { return nLeft; } else if(nRight != null) { return nRight; } return null; }
以下公共方法调用上面的私有递归版本：
public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2) { var n = this.FindNode(this._root, e1); if(null == n) { throw new Exception("Element not found: " + e1); } if (e1 == e2) { return n; } n = this.FindNode(this._root, e2); if (null == n) { throw new Exception("Element not found: " + e2); } var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2); if (null == node) { throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2)); } return node; }
通过跟踪两个节点的路径来解决：
public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2) { var path1 = new List(); var node1 = this.FindNodeAndPath(this._root, e1, path1); if(node1 == null) { throw new Exception(string.Format("Element {0} is not found", e1)); } if(e1 == e2) { return node1; } List path2 = new List (); var node2 = this.FindNodeAndPath(this._root, e2, path2); if (node1 == null) { throw new Exception(string.Format("Element {0} is not found", e2)); } BinaryTreeNode lca = null; Debug.Assert(path1[0] == this._root); Debug.Assert(path2[0] == this._root); int i = 0; while((i < path1.Count) && (i < path2.Count) && (path2[i] == path1[i])) { lca = path1[i]; i++; } Debug.Assert(null != lca); return lca; }
其中FindNodeAndPath定义为
private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List path) { if(node == null) { return null; } if(node.Element == e) { path.Add(node); return node; } var n = this.FindNodeAndPath(node.Left, e, path); if(n == null) { n = this.FindNodeAndPath(node.Right, e, path); } if(n != null) { path.Insert(0, node); return n; } return null; }
BST（LCA） - 无关（仅供完成参考）
public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2) { //ensure both elements are there in the bst var n1 = this.BstFind(e1, throwIfNotFound: true); if(e1 == e2) { return n1; } this.BstFind(e2, throwIfNotFound: true); BinaryTreeNode leastCommonAcncestor = this._root; var iterativeNode = this._root; while(iterativeNode != null) { if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2)) { iterativeNode = iterativeNode.Left; } else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2)) { iterativeNode = iterativeNode.Right; } else { //ie; either iterative node is equal to e1 or e2 or in between e1 and e2 return iterativeNode; } } //control will never come here return leastCommonAcncestor; }
unit testing
[TestMethod] public void LeastCommonAncestorTests() { int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 }; int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22}; BinarySearchTree bst = new BinarySearchTree(); foreach (int e in a) { bst.Add(e); bst.Delete(e); bst.Add(e); } for(int i = 0; i < b.Length; i++) { var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]); Assert.IsTrue(n.Element == b[i]); var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]); Assert.IsTrue(n1.Element == b[i]); Assert.IsTrue(n == n1); var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]); Assert.IsTrue(n2.Element == b[i]); Assert.IsTrue(n2 == n1); Assert.IsTrue(n2 == n); } }