这里的二叉树不一定是二叉搜索树。 该结构可以视为-
struct node { int data; struct node *left; struct node *right; };
我可以和朋友一起解决的最大解决方案就是这种情况- 考虑以下二叉树：
有序遍历收益-8，4，9，2，5，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）的时间复杂度算法是最好的，如果你没有父指针，你可以做。）对于算法的一个简单的递归版本中看到代码金丁的职务)它运行在O（n）的时间。
但是请记住，如果您的节点具有父指针，则可以使用改进的算法。对于有问题的两个节点，请从节点开始并在前面插入父节点，以构建一个包含从根到节点的路径的列表。
因此，对于您的示例中的8，您得到了（显示步骤）：{4}，{2、4}，{1、2、4}
对您所讨论的其他节点执行相同的操作，导致（未显示步骤）：{1，2}
现在比较您创建的两个列表，以查找列表不同的第一个元素，或列表中一个的最后一个元素，以先到者为准。
该算法需要O（h）时间，其中h是树的高度。在最坏的情况下，O（h）等于O（n），但是如果树是平衡的，则只有O（log（n））。它还需要O（h）空间。可能只使用恒定空间的改进版本，代码在CEGRD的帖子中显示
不管如何构造树，如果这是您对树执行多次操作而又不改变树之间的操作，则可以使用其他算法，这些算法需要O（n）[线性]时间准备，但是要找到配对仅需O（1）[恒定]时间。有关这些算法的参考，请参见[Wikipedia上最低的祖先问题页面。（感谢Jason最初发布了此链接）
