python最低共同祖先

在Python中實現最低共同祖先最簡單的方法是什麼？我有一棵樹，每個節點都有一個指向父節點的指針，我希望能夠找到給定兩個節點的第一個共同祖先。我想出了一些想法，但沒有特別吸引python最低共同祖先

讓每個節點包含其基地的名單，並進行聯接，發現最長的公共前綴，然後把最後一個元素。不幸的是，我不知道任何內置的方法來做最長的通用前綴，所以這需要手動循環。
讓每個節點都包含一組基，並執行一組交集，並取最大元素。但是這需要定義自定義比較運算符，我甚至不確定它是否可行。

我該怎麼辦？我正在尋找一些有利於簡化性能的解決方案，因此需要複雜處理的解決方案已經無法使用。

編輯：我發現，雖然沒有內置的方式，你可以使用zip在一行中做最長的通用前綴，所以它仍然相當簡單。

common = [x for x in zip(*baselists) if len(set(x)) == 1][-1]

來源

2012-08-10 Antimony

下，你不能修改你的樹，包括深度的假設，你可以做到以下幾點：

對於每個節點，遞歸向上遍歷樹，直到你打根。在每個父節點處，將節點插入list。這應該給你list_a和list_b。迭代最短列表，比較每個列表中的元素。當你找到一個不匹配的地方時，先前的條目就是你最大的父元素。

來源

2012-08-10 17:22:32 aaronlevin

如果您可以在不修改樹本身的情況下計算深度不得不。只需使用遞歸函數或迭代節點的祖先即可。 – 2012-08-10 17:34:51

取每個節點的深度（距離根的距離）。如果其中一個低於另一個，則從較低節點向上到樹的深度相等。然後檢查身份，每次檢查失敗時在每一邊移動每個身份。

你可以用一個while循環做到這一點。一旦你選擇了以同樣深度的祖先：

while (ancestorA !== ancestorB) { 
    ancestorA = ancestorA.parent(); 
    ancestorB = ancestorB.parent(); 
}

當while循環結束，ancestorA和ancestorB將分別成爲你的共同祖先。

這應該不僅很簡單，而且相當快。

來源

2012-08-10 17:03:33

有什麼辦法修改此所以它不需要兩個循環？ – Antimony 2012-08-10 17:40:23

如果你不能得到深度？上面的算法根本沒有幫助。然而，即使深度沒有存儲在樹中，在每一步中保存父母列表並與其他祖先進行比較也會得出結果。雖然，這需要反覆循環遍歷可能會減慢速度的祖先列表。 – aneroid 2012-08-11 07:44:19

您可以編寫一個簡單的函數，通過遞歸或遍歷祖先節點來獲取深度。在節點/樹上定義方法只是OO設計的一個很好的方便/功能。 – 2012-08-12 13:51:51

我想它取決於你的樹，它將包含多少個對象。如果這個數字在記憶方面是合理的（可能少於幾百萬個節點，但這只是我的猜測），我會用你的建議＃2。在該集合中，只需保留每個基的字符串表示形式，因此內置的比較就可以工作。應該非常快，我想你可以用幾行代碼來實現它。如果字符串表示形式不實際，或者如果您需要對象本身並且無法實現所有對象的主字典，只需在您的節點對象中定義比較方法（如果我記得，則爲eq和neq）。

來源

2012-08-10 17:47:10 DaveTheScientist

想法它保持父母收集，最好使用散列映射=，因爲在這種情況下，你不會花費在家長列表搜索。因此，在每次迭代時檢查這張地圖，如果當前節點的父親已經存在於地圖中，那麼這個父母就是你的結果。在最壞的情況下，它會給出O（n），但是如果您在某些情況下將開始分析兩個節點，您將能夠更快地找到它。

來源

2012-08-10 22:02:48

既然你已經有一個指針，在兩種情況下的父節點爲什麼不這樣做：（類似於weirdcanada說，但...）

創建每個節點的父母的列表，在列表建設順序每個階段。所以list_a和list_b隨着你走高而增長。比較每個列表中添加的最後一個項目與另一個項目的項目。只要list_a中的項目與list_b中的項目匹配，您就擁有最低的共同祖先。

while (parent_a not in list_b) or (parent_b not in list_a): 
    ...

您不需要一直重建鏈，直到root。無論如何，你將不得不依次檢查每個父母（向前或向後）。

來源

2012-08-11 07:33:47 aneroid

這是一個O（n^2）算法。我知道原始的海報說他想要簡單性以上的表現，但如果樹足夠高，這個算法將表現得非常糟糕。 – 2012-08-12 13:54:50

好吧，夠公平的。然後......（繼續你的回答）...... – aneroid 2012-08-12 16:32:05

Python有內置集合。爲什麼不使用沿（僞代碼）線的東西：

a_ancestors = set() 
while a: 
    a_ancestors.add(a) 
    a = a.parent 

while b: 
    if b in a_ancestors: 
    return b 
    b = b.parent 

return None # <- can't reach that for a *tree* !!!

這將生成節點一個的所有祖先的（無序）集（包括一個本身）。

然後，在第二次，我們循環所有的祖先b。根據定義，b的第一個祖先是a的祖先將是第一個共同的祖先。這部作品在爲O（n）（在空間和時間）

你有可能加快這一進程（最終在空間佔用爲代價）通過同時收集兩個組的祖先一個和b - 一找到一個公共節點就停下來。該代碼是有點做作，你必須處理的一個分支，已達到之前其他根：

visited = set() 
while a or b: 
    if a: 
    if a in visited: 
     return a 
    visited.add(a) 
    a = a.parent 

    if b: 
    if b in visited: 
     return b 
    visited.add(b) 
    b = b.parent 

return None # <- can't reach that for a *tree* !!!

來源

2016-03-10 21:35:22

python最低共同祖先

回答

相關問題