檢查葉子c是否與葉子a和葉子b在同一子樹中的最有效算法

Question

目前，我正在研究一個程序，其中一個步驟是檢查葉子c是否與另外兩個葉子在相同的子樹中a和b在二叉樹T中。我目前的方法如下：首先，找到T中每對葉子的LCA，並將其存儲在字典中。然後，對於樹中的每個節點，查找所有樹葉的後代，並將其存儲在字典中。然後，當我需要確定c是否與a和b在同一子樹中時，我找到a和b的LCA，並檢查c是它的後代。

我需要爲許多不同的對a和b運行此步驟，並且在具有多達600個葉子的二叉樹上執行此操作，所以有更快的算法，或者使用更少的內存，這同樣的任務？謝謝。

Answer 1

一個有用的觀察，可以幫助你在這裏如下：含葉一個和b最小的子樹是在LCA根的子樹（一個，b）。這意味着，可以測試Ç是否處於子樹通過檢查Ç是否是LCA的後代（一個，b）。一種方法是：計算LCA（LCA（a,b），c）。如果Ç是在此子樹，然後LCA（LCA（一個，b）Ç）= LCA（一個，b）。否則，它將是其他節點。這給出了一個很好的算法：

返回是否LCA（LCA（一個，b）Ç）= LCA（一個，b）。

這也可能有助於使用快速的LCA數據結構。您提到預先計算樹中所有節點對的LCA，但有更快的選項。特別是，有一些很好的算法，通過O（n）預處理時間可以在時間O（1）中返回樹中兩個節點的LCA。如果您事先知道這些配對，請查看Tarjan's offline LCA algorithm;如果沒有，請查看Fischer-Heun LCA data structure。

希望這會有所幫助！