树如何找共同祖先_如何找到任何二叉树中两个节点的最低公共祖先？

小编典典

尼克·约翰逊是正确的，一个一个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最初发布了此链接)

2020-07-28

总结

以上是生活随笔为你收集整理的树如何找共同祖先_如何找到任何二叉树中两个节点的最低公共祖先？的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。