給定一棵樹，在Log（n）中找到從節點'a'到節點'b'的路徑中的第k個節點？

Question

給定一棵樹，我需要找到從'a'到'b'的路徑中'第k個節點。這意味着我需要在從節點'a'到節點'b'的路徑中的'第k'位置找到節點。我正在思考最低共同祖先和/或重光分解的問題，但我不確定這是否是這樣做的。任何正確的方向指導表示讚賞。

詳情：

• 的樹不是二叉樹。它是一個具有n-1個邊，n個頂點和無週期的無向圖。只是你的常規樹
• 樹的頂點編號從1到n。有n-1個無向邊連接這些頂點的n-1對
• 'a'和'b'是樹中從1到n編號的任何2個頂點。我們要在從'a'到'b'的路徑中找到'第k個節點。這是保證數「k」的值是< =從路徑中的節點的數目「A」到「b」

甲BFS施加在每個查詢（第k個節點從「A」到「b」 ）不是一個選項，因爲查詢的數量很大。

Answer 1

做最低的共同祖先，並保持每個節點的深度（距根的距離）。

接下來找出第k個節點是否位於a到lca或lca到b的一部分。深度差異是它們之間的節點數量，所以如果depth[a] - depth[lca] > k那麼該節點位於lca-b部分。

如果節點位於a到lca部分，只需找到第k個祖先。應該使用您預先計算的LCA數據記錄（N）。

如果節點位於b到lca部分，則可以計算k'，這是距第b個節點（k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k)）第k個節點的距離，然後獲得b的k'祖先（使用LCA數據也很容易）。

總體而言，所有查找都是logN，其他步驟都是常量，因此您需要爲每個查詢執行O（LogN）。