給定節點對的最低公共祖先

Question

我被這個問題偶然發現。以下是我的做法：

Lets say the two nodes are node1 and node2 
For any node (lets say node1), find the path from Root to 
     node1 and store it in an HashMap 
For the other node node2, find the path from root to node2, and while traversing back, 
     check if any of the nodes are present in the hashmap or not 
Return the first found node 

時間複雜度爲O（n）和空間複雜度也是O（h）時，其中n是樹的高度

我只是想知道有多好，這種方法。或者是否存在其他更好的解決方案。

編輯：給定的樹是二叉樹，而不是BST。因此，查找節點所花的時間與節點的大小是線性的。

Answer 1

如果你只需要這樣做一次（或幾次），那麼這是一個好方法（如果可能的話，你可以通過從節點到根的方式進行優化）。如果你需要爲不同的節點對做很多次這樣的事情，那麼花費更多的時間對某些事情進行預計算是值得的，這將加快查詢速度。

我認爲this article解釋得很好。如果您有任何問題，請發回。

Answer 2

樹如何表示？特別是，是否有對任何樹節點的父節點的引用？它是一棵有序的樹嗎？

計算從節點到根的路徑並不比較簡單，然後比較從根節點到節點的路徑？兩條路徑上的最後一個節點是共同的祖先。

我想找到從根到節點的路徑（如你的做法有它）是O（n），其中n是樹的大小，除非樹是有序的...

所以你的方法作品，但如果我問你的問題，我本來希望你問一些關於樹的佈局的額外問題，以確定正確的答案...

Answer 3

這裏是解決最低公共祖先問題的指令。

[範圍最小查詢和最近公共祖先] [1]

[1]：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest共同祖先（LCA）