爲兩個節點尋找最接近的父親

Question

尋找樹上兩個給定節點的最親密父母的最佳方法是什麼？
所以，如果我有：

   1 
      / \ 
      2  3 
      /\ /\ 
      4 5 6 7 

最接近父5和6是一個。
謝謝

Answer 1

此問題被稱爲最低公共祖先（LCA）問題。

的第一步就是讓下層節點爬升，直到他們都在同一height：（谷歌它）

一個查詢可以通過簡單地沿着其parent鏈接爬起來，直到他們滿足回答。

第二步是讓他們同時攀登，直到他們在同一節點相遇。

那麼那個節點就是這兩個節點的LCA。

如果您需要處理多個查詢，則需要使用更高級的算法。最具時間效率的算法使用O（n）時間進行預處理，並且O（1）時間爲每個查詢，其中n是樹中的總節點。