如何確定節點w是否位於樹中節點u和節點v之間的路徑中？

我想解決一個問題，需要我確定一個節點是否位於節點u和節點v之間的路徑中（不一定是二進制）。如何確定節點w是否位於樹中節點u和節點v之間的路徑中？

例如，對於下面的樹：

1 
    2 3 
4 5 6 7

節點2個位於從節點4的路徑上至7

一個明顯的解決方案將是，以獲得樹和橫越的歐拉回路在兩個節點的第一次出現之間訪問的節點。但是，在最壞的情況下，這將是一個O（n）解決方案，其中n是樹中節點的數量。我在某處讀到，這可以使用LCA（最低共同祖先）完成。但是，我似乎無法理解如何。有人能告訴我嗎？

2017-06-20 LanceHAOH

你想要學習LCA或解決問題的建議嗎？說如果你有一個黑盒O（h）算法找到LCA，你知道如何使用LCA來解決它嗎？ – shole

我知道如何使用稀疏表和RMQ在樹中找到2個節點的LCA。我想解決這篇文章中描述的問題。我剛剛讀到使用LCA可以有效解決問題。也許可以用其他方法解決。但我不明白LCA或其他方法如何解決這個問題。 – LanceHAOH

我認爲如果滿足以下兩個條件，答案是肯定的？（w，v）= w 2. lca（w，x）= x – shole

說A = LCA（u，v）。 u和v之間的路徑是從u到a和從a到v的路徑。檢查每個節點（從u上升，然後從v上升）。如果w在他們之中，那麼它就在路上，否則它不在。

2017-06-20 11:04:38 Dave

這是有效的，但在最壞的情況下也是O（n）時間（如果允許有1個孩子的頂點;如果每個頂點至少有2個孩子，則爲O（log n）），因爲深度也是上界的O（log n）。） –

@j_random_hacker你認爲有可能比從u到v的路徑的長度要好嗎？ – Dave

shole對該問題的評論描述了在O（1）中做到這一點的一種方法。（我實際上寫了一個「暗示」的回答，描述了同樣的事情，然後才意識到信息已經存在......） –

回答