二叉樹的最低公共祖先（不是二叉搜索樹）

我試着從網站上使用Tarjan算法和一種算法來解決問題：http://discuss.techinterview.org/default.asp?interview.11.532716.6，但沒有一個是清楚的。也許我的遞歸概念不適當地建立。請給出一個小示範來解釋上述兩個例子。我有聯盟查找數據結構的想法。二叉樹的最低公共祖先（不是二叉搜索樹）

它看起來很有趣的問題。無論如何，必須解決問題。準備面試。

如果存在其他邏輯/算法，請分享。

來源

2010-08-22 AGeek

LCA算法試圖做一件簡單的事情：找出從問題的兩個節點到根的路徑。現在，這兩條路徑會有一個共同的後綴（假設路徑以根結尾）。 LCA是後綴開始的第一個節點。

考慮下面的樹：

   r * 
      /\ 
      s * * 
      /\ 
      u * * t 
     //\ 
      * v * * 
      /\ 
      * *

爲了找到LCA（U，V），我們進行如下操作：

路徑從u到根：路徑（（v，r）= vtsr

現在，我們檢查了常見的後綴：

通用後綴： 'SR'
因此LCA（U，V）=後綴的第一個節點= S

注意實際算法不要一路走到根。當它們到達s時，它們使用Disjoint-Set數據結構來停止。

一組優秀的替代方法解釋爲here。

來源

2010-08-22 07:57:39 dirkgently

只有一點評論：樹木往往（主要）平衡。在這些情況下，使用不相交集合數據結構的開銷可能比僅從u標記根，然後從v。 – Rafe 2010-08-23 03:13:40

既然你提到了工作面試，我想到了你只限於O（1）內存使用的這個問題的變化。

在這種情況下，考慮下面的算法：

1）從節點u到根掃描樹，找到的路徑長度L（U）

2）掃描從結點V的樹（v）

3）計算路徑長度差D = | L（u）-L（v）|

4）在從根部

5）走了樹中從兩個節點並行，直到到達同一節點

6）返回該節點作爲較長路徑跳過d節點LCA

來源

2010-08-22 09:16:18

-1

假設您只需要解決問題一次（每個數據集），那麼一個簡單的方法是從一個節點（和它自己）收集祖先集，然後從另一個節點走祖先列表直到你會發現上面一組的成員，它必然是最低的共同祖先。該僞碼給出：

Let A and B begin as the nodes in question. 
seen := set containing the root node 
while A is not root: 
    add A to seen 
    A := A's parent 
while B is not in seen: 
    B := B's parent 
B is now the lowest common ancestor.

另一種方法是計算整個路徑到房間的每個節點，然後從尋找一個共同後綴右掃描。它的第一個元素是LCA。哪一個更快取決於你的數據。

如果你也將需要尋找許多節點對LCA的，那麼你就可以做出各種空間/時間權衡：

你可以，例如，預先計算每個節點的深度，這將允許您避免每次重新創建集（或路徑）時首先從較深的節點行進到較淺節點的深度，然後在鎖步驟中將兩個節點向根行走：當這些路徑相遇時，您有LCA。

另一種方法在depth-mod-H註釋其下一個祖先的節點，以便首先解決類似但是H次小問題，然後解決第一個問題的H大小實例。這對於非常深的樹木是很好的，並且通常選擇H作爲樹的平均深度的平方根。

來源

2010-08-22 14:44:00 Ian

向上搜索第一個標記節點的根開銷，如果允許，您可以做得更好預處理樹。 – Ian 2010-08-22 14:48:10

二叉樹的最低公共祖先（不是二叉搜索樹）

回答

相關問題