尋找最少在二叉樹中的共同祖先o（h^2）換一個

Question

在考慮寫一個函數來實現它之前，我試着想一個算法。 h被表示爲主父節點與給定節點之間的最大距離。它應該運行在o（h^2）這意味着它應該更容易提出這樣一個算法，但我經常發現自己與o（h）算法。當談到了解我是否真的在做h^2操作時，我也感到困惑。我真的可以用鉛。

Answer 1

最簡單的LCA算法將在O(h^2)中運行 - 創建兩個嵌套循環，一個運行在第一個頂點的所有祖先上，另一個運行在第二個頂點的所有祖先上，並在循環內部比較它們。

a1 = a // a is the first given vertes 
while a1 != nil // assume root's parent is nil 
    a2 = b // b is the second given vertex 
    while a2 != nil 
     if (a1 == a2) 
      compare with current-best solution 
     a2 = a2.parent 
    a1 = a1.parent 

因此，從第一個給定的頂點開始，即通過它的所有祖先。對於它的祖先a1，從第二個給定的頂點到根，並檢查您是否遇到路上的a1頂點。