二叉树的最低共同祖先
这是一个受欢迎的访谈问题，我可以在这个主题上找到的唯一一篇文章来自TopCoder 。 对我来说不幸的是，从面试答案的角度看，它看起来过于复杂。
除了绘制两个节点的路径并推断祖先之外，是否有更简单的方法可以做到这一点？ （这是一个很受欢迎的答案，但是面试问题的变化需要一个恒定的空间答案）。
恒定空间答案:(虽然不一定有效）。
有一个函数findItemInPath（int index，int searchId，Node root）
然后从0深度的树迭代，在两个搜索路径中找到第0项，第1项等。
当你发现i使得函数为两者返回相同的结果，而不是i + 1时，那么路径中的第i个项是最低的共同祖先。
一个简单的（但更少涉及的版本）可能只是（.NET在这里Java有点生疏，所以请原谅语法，但我认为你不必调整太多）。 这就是我一起扔的东西。
class Program { static void Main(string[] args) { Node node1 = new Node { Number = 1 }; Node node2 = new Node { Number = 2, Parent = node1 }; Node node3 = new Node { Number = 3, Parent = node1 }; Node node4 = new Node { Number = 4, Parent = node1 }; Node node5 = new Node { Number = 5, Parent = node3 }; Node node6 = new Node { Number = 6, Parent = node3 }; Node node7 = new Node { Number = 7, Parent = node3 }; Node node8 = new Node { Number = 8, Parent = node6 }; Node node9 = new Node { Number = 9, Parent = node6 }; Node node10 = new Node { Number = 10, Parent = node7 }; Node node11 = new Node { Number = 11, Parent = node7 }; Node node12 = new Node { Number = 12, Parent = node10 }; Node node13 = new Node { Number = 13, Parent = node10 }; Node commonAncestor = FindLowestCommonAncestor(node9, node12); Console.WriteLine(commonAncestor.Number); Console.ReadLine(); } public class Node { public int Number { get; set; } public Node Parent { get; set; } public int CalculateNodeHeight() { return CalculateNodeHeight(this); } private int CalculateNodeHeight(Node node) { if (node.Parent == null) { return 1; } return CalculateNodeHeight(node.Parent) + 1; } } public static Node FindLowestCommonAncestor(Node node1, Node node2) { int nodeLevel1 = node1.CalculateNodeHeight(); int nodeLevel2 = node2.CalculateNodeHeight(); while (nodeLevel1 > 0 && nodeLevel2 > 0) { if (nodeLevel1 > nodeLevel2) { node1 = node1.Parent; nodeLevel1--; } else if (nodeLevel2 > nodeLevel1) { node2 = node2.Parent; nodeLevel2--; } else { if (node1 == node2) { return node1; } node1 = node1.Parent; node2 = node2.Parent; nodeLevel1--; nodeLevel2--; } } return null; } } 文章解决方案更复杂的主要原因是它处理两阶段问题 – 预处理然后查询 – 而你的问题听起来好像你只做一个查询所以预处理没有意义。 它还处理任意树而不是二叉树。
最好的答案肯定取决于树的细节。 对于许多种树，时间复杂度将是O（h），其中h是树的高度。 如果你有指向父节点的指针，那么简单的“恒定空间”答案就像在Mirko的解决方案中一样，找到两个节点的高度并比较相同高度的祖先。 请注意，这适用于具有父链接，二进制或否的任何树。 我们可以通过迭代高度函数并从主循环中分离“获取相同深度”循环来改进Mirko的解决方案：
int height(Node n){ int h=-1; while(n!=null){h++;n=n.parent;} return h; } Node LCA(Node n1, Node n2){ int discrepancy=height(n1)-height(n2); while(discrepancy>0) {n1=n1.parent;discrepancy--;} while(discrepancy<0) {n2=n2.parent;discrepancy++;} while(n1!=n2){n1=n1.parent();n2=n2.parent();} return n1; }
“恒定空间”周围的引号是因为通常我们需要O（log（h））空间来存储它们之间的高度和差异（例如，3个BigIntegers）。 但是如果你处理的树木高度太大而不能长时间存在，那么你可能还有其他问题需要担心，这比存储几个节点的高度更加紧迫。
如果您有BST，那么您可以轻松地采用共同的祖先（usu。从root开始）并检查其子项以查看它们中的任何一个是否是共同的祖先：
Node LCA(Node n1, Node n2, Node CA){ while(true){ if(n1.valCA.val & n2.val>CA.val) CA=CA.right; else return CA; } }
正如Philip JF所提到的，同样的想法可以在任何树中用于恒定空间算法，但是对于一般树来说这样做会非常缓慢，因为重复计算CA.left或CA.right是否是共同的祖先会重复很多工作，所以你通常更喜欢使用更多的空间来节省一些时间。 做出这种权衡的主要方式基本上就是你提到的算法（存储来自root的路径）。
重要的是你正在使用什么样的树。 您始终可以判断一个节点是否是恒定空间中另一个节点的祖先，并且顶部节点始终是一个共同的祖先，因此将最低公共祖先放在恒定空间中只需要迭代。 在二叉搜索树上，这很容易快速完成，但它可以在任何树上工作。
许多不同的权衡取决于这个问题，树的类型很重要。 如果您有指向父节点的指针，而不仅仅是对子节点（Mirko的代码使用它），问题往往会容易得多
另见： http ： //en.wikipedia.org/wiki/Lowest_common_ancestor
使用log（n）空间的明显解决方案（n是节点数）是您提到的算法。 这是一个实现。 在最坏的情况下，它花费O（n）时间（假设您正在搜索共同祖先的节点之一包括最后一个节点）。
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication2 { class Node { private static int counter = 0; private Node left = null; private Node right = null; public int id = counter++; static Node constructTreeAux(int depth) { if (depth == 0) return null; Node newNode = new Node(); newNode.left = constructTree(depth - 1); newNode.right = constructTree(depth - 1); return newNode; } public static Node constructTree(int depth) { if (depth == 0) return null; Node root = new Node(); root.left = constructTreeAux(depth - 1); root.right = constructTreeAux(depth - 1); return root; } private List findPathAux(List pathSoFar, int searchId) { if (this.id == searchId) { if (pathSoFar == null) pathSoFar = new List (); pathSoFar.Add(this); return pathSoFar; } if (left != null) { List result = left.findPathAux(null, searchId); if (result != null) { result.Add(this); return result; } } if (right != null) { List result = right.findPathAux(null, searchId); if (result != null) { result.Add(this); return result; } } return null; } public static void printPath(List path) { if (path == null) { Console.Out.WriteLine(" empty path "); return; } Console.Out.Write("["); for (int i = 0; i < path.Count; i++) Console.Out.Write(path[i] + " "); Console.Out.WriteLine("]"); } public override string ToString() { return id.ToString(); } /// /// Returns null if no common ancestor, the lowest common ancestor otherwise. /// public Node findCommonAncestor(int id1, int id2) { List path1 = findPathAux(null, id1); if (path1 == null) return null; path1 = path1.Reverse ().ToList (); List path2 = findPathAux(null, id2); if (path2 == null) return null; path2 = path2.Reverse ().ToList (); Node commonAncestor = this; int n = path1.Count < path2.Count? path1.Count : path2.Count; printPath(path1); printPath(path2); for (int i = 0; i < n; i++) { if (path1[i].id == path2[i].id) commonAncestor = path1[i]; else return commonAncestor; } return commonAncestor; } private void printTreeAux(int depth) { for (int i = 0; i < depth; i++) Console.Write(" "); Console.WriteLine(id); if (left != null) left.printTreeAux(depth + 1); if (right != null) right.printTreeAux(depth + 1); } public void printTree() { printTreeAux(0); } public static void testAux(out Node root, out Node commonAncestor, out int id1, out int id2) { Random gen = new Random(); int startid = counter; root = constructTree(5); int endid = counter; int offset = gen.Next(endid - startid); id1 = startid + offset; offset = gen.Next(endid - startid); id2 = startid + offset; commonAncestor = root.findCommonAncestor(id1, id2); } public static void test1() { Node root = null, commonAncestor = null; int id1 = 0, id2 = 0; testAux(out root, out commonAncestor, out id1, out id2); root.printTree(); commonAncestor = root.findCommonAncestor(id1, id2); if (commonAncestor == null) Console.WriteLine("Couldn't find common ancestor for " + id1 + " and " + id2); else Console.WriteLine("Common ancestor for " + id1 + " and " + id2 + " is " + commonAncestor.id); } } }
这里描述的自下而上的方法是O（n）时间，O（1）空间方法：
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
Node *LCA(Node *root, Node *p, Node *q) { if (!root) return NULL; if (root == p || root == q) return root; Node *L = LCA(root->left, p, q); Node *R = LCA(root->right, p, q); if (L && R) return root; // if p and q are on both sides return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees }