這個最不常見的祖先算法有什麼問題？

給出一個根節點（到井形成二叉樹）和其他兩個節點（這是保證在樹上，並且也不同），返回兩個節點的最低共同祖先。

我不知道任何最不常見的祖先算法，所以我試圖在現場製作一個。我公司生產的以下代碼：

def least_common_ancestor(root, a, b): 
    lca = [None] 
    def check_subtree(subtree, lca=lca): 
     if lca[0] is not None or subtree is None: 
      return 0 

     if subtree is a or subtree is b: 
      return 1 
     else: 
      ans = sum(check_subtree(n) for n in (subtree.left, subtree.right)) 

     if ans == 2: 
      lca[0] = subtree 
      return 0 

     return ans 

    check_subtree(root) 

    return lca[0] 


class Node: 
    def __init__(self, left, right): 
     self.left = left 
     self.right = right

我試着下面的測試案例，並得到了我所期望的答案：

a = Node(None, None) 
b = Node(None, None) 

tree = Node(Node(Node(None, a), b), None) 
tree2 = Node(a, Node(Node(None, None), b)) 
tree3 = Node(a, b)

，但我的面試官告訴我說：「有一類的樹木，你的算法返回None。「我無法弄清楚它是什麼，而且我忽視了採訪。我想不出一個算法會使它到達樹的底部而沒有ans永遠變成2的情況 - 我錯過了什麼？

來源

2014-12-07 Patrick Collins

現在讓'b'成爲'a'的子節點，反之亦然。 – 2014-12-07 10:43:43

@MartijnPieters啊，謝謝，就是這樣。如果你能夠做出答案，我很樂意接受。否則，也許我應該刪除這個問題？ – 2014-12-07 10:46:05

你似乎認爲a和b在它們的lca的不同子樹中。這不是一個好的假設。從邊界案例開始。 'a是b'，'a是根'，樹只剩下分支等。你會感到驚訝。 – 2014-12-07 10:51:00

你忘了說明a是b的直接祖先，反之亦然。您找到任一節點後立即停止搜索並返回1，因此在這種情況下您將永遠找不到其他節點。

給您一個格式良好的二叉搜索樹;這種樹的一個屬性是，您可以根據它們與當前節點的相對大小輕鬆找到元素;更小的元素進入左邊的子樹，更大的進入右邊。因此，如果您知道兩個元素都在樹中，您只需要比較鍵;只要您找到兩個目標節點之間的之間的節點，或者等於其中一個節點，就會找到最低的共同祖先。

你的樣品節點從來沒有包括在存儲密鑰的樹，這樣你就不能使用這個屬性的，但如果你做，你會使用：

def lca(tree, a, b): 
    if a.key <= tree.key <= b.key: 
     return tree 
    if a.key < tree.key and b.key < tree.key: 
     return lca(tree.left, a, b) 
    return lca(tree.right, a, b)

如果樹只不過是一個'常規'二叉樹，而不是搜索樹，唯一的選擇是找到兩個元素的路徑並找到這些路徑分歧的點。

如果您的二叉樹維護父引用和深度，這可以高效地完成;直接走到兩個節點的深處，直到深度相同，然後從兩個節點向上繼續，直到找到一個公共節點;那是最不常見的祖先。

如果您沒有這兩個元素，您必須從根開始找到兩個節點分別搜索的路徑，然後找到這兩個路徑中的最後一個公共節點。

來源

2014-12-07 10:51:30

樹不能保證排序或有鍵。我不相信「二叉樹」意味着「二叉搜索樹」。 – 2014-12-07 11:02:56

@PatrickCollins：對，這是一個重要的區別。你允許用深度註釋節點嗎？ – 2014-12-07 11:05:33

寫在最上面的問題是我得到的完整提示。我後來給出了一個答案，即面試官認爲是正確的，包括建立從根到'a'的路徑，並從根到'b'，然後檢查該路徑的交集。 – 2014-12-07 11:06:55

您錯過了a是b的祖先的情況。

看看這個簡單的反例：

a 
    b None

a也給出root，並調用該函數時，可以調用check_subtree(root)，這是a，那麼你會發現，這是你在找什麼for（在返回1的停止子句中），並且在沒有設置lca的情況下自動返回1。

來源

2014-12-07 10:47:31 amit

這個最不常見的祖先算法有什麼問題？

回答

相關問題