这里的二叉树不一定是二叉搜索树。 该结构可以被视为 -
struct node { int data; struct node *left; struct node *right; };
我可以与朋友一起解决的最大解决方案是这种类型的 - 考虑一下这个二叉树：
中序遍历产生 - 8, 4, 9, 2, 5, 1, 6, 3, 7
并且后序遍历产生 - 8, 9, 4, 5, 2, 6, 7, 3, 1
例如，如果我们想找到节点 8 和 5 的共同祖先，那么我们在中序树遍历中列出所有介于 8 和 5 之间的节点，在这种情况下恰好是 [4, 9 , 2]。然后我们检查这个列表中的哪个节点在后序遍历中最后出现，即 2。因此 8 和 5 的共同祖先是 2。
这个算法的复杂性，我相信是 O(n) （O(n) 用于中序/后序遍历，其余步骤也是 O(n)，因为它们只不过是数组中的简单迭代）。但很有可能这是错误的。:-)
但这是一种非常粗糙的方法，我不确定它是否会在某些情况下失效。这个问题还有其他（可能更优化）的解决方案吗？
尼克约翰逊是正确的，如果你没有父指针，那么 O(n) 时间复杂度算法是你能做的最好的。）
但请记住，如果您的节点具有父指针，则可以使用改进的算法。对于有问题的两个节点，通过从节点开始并在前面插入父节点，构造一个包含从根到节点的路径的列表。
因此，对于您的示例中的 8，您会得到（显示步骤）：{4}、{2、4}、{1、2、4}
对有问题的其他节点执行相同操作，导致（未显示步骤）：{1, 2}
现在比较您创建的两个列表，寻找列表不同的第一个元素，或其中一个列表的最后一个元素，以先到者为准。
该算法需要 O(h) 时间，其中 h 是树的高度。在最坏的情况下，O(h) 等价于 O(n)，但如果树是平衡的，那就只有 O(log(n))。它还需要 O(h) 空间。一个改进的版本是可能的，它只使用常量空间，代码显示在CEGRD的帖子中
到目前为止给出的答案使用递归或存储，例如，内存中的路径。
如果你的树很深，这两种方法都可能会失败。
这是我对这个问题的看法。当我们检查两个节点的深度（到根的距离）时，如果它们相等，那么我们可以安全地从两个节点向上移动到共同的祖先。如果其中一个深度较大，那么我们应该从较深的节点向上移动，同时留在另一个节点。
这是代码：
findLowestCommonAncestor(v,w): depth_vv = depth(v); depth_ww = depth(w); vv = v; ww = w; while( depth_vv != depth_ww ) { if ( depth_vv > depth_ww ) { vv = parent(vv); depth_vv--; else { ww = parent(ww); depth_ww--; } } while( vv != ww ) { vv = parent(vv); ww = parent(ww); } return vv;
该算法的时间复杂度为：O(n)。该算法的空间复杂度为：O(1)。
关于深度的计算，我们首先可以记住定义：如果v是根，depth(v) = 0；否则，depth(v) = depth(parent(v)) + 1。我们可以如下计算深度：
depth(v): int d = 0; vv = v; while ( vv is not root ) { vv = parent(vv); d++; } return d;
不管树是如何构造的，如果这将是您在树上执行多次而不在两者之间更改它的操作，那么您可以使用其他需要 O(n) [线性] 时间准备的算法，然后找到任何pair 只需要 O(1) [常数] 时间。有关这些算法的参考，请参阅Wikipedia上最低的共同祖先问题页面。（感谢 Jason 最初发布此链接）
