小編典典

尼克·約翰遜是正確的，一個一個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

總結

以上是生活随笔為你收集整理的树如何找共同祖先_如何找到任何二叉树中两个节点的最低公共祖先？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。