最低公共祖先 - 代碼說明

Question

LCA通過順序和後序遍歷很容易實現和理解我。

但是，有一個遞歸的自下而上的方法。

我看了一下代碼網上，我不明白一個行：

下面是代碼：

public Node lowestCommonAncestor(int val1, int val2,Node root){ 
    if(root == null){ 
     return null; 
    } 
    if(root.data == val1 || root.data == val2){ 
     return root; 
    } 

    Node left = lowestCommonAncestor(val1, val2, root.left); 
    Node right = lowestCommonAncestor(val1, val2, root.right); 

    if(left != null && right != null){ 
     return root; 
    } 
    return left != null ? left : right; 
} 

val1和val2的是兩個節點的值，其LCA必須找到。

最後一行是我卡在哪裏。

return left != null ? left : right; 

有人可以解釋這一點嗎？

謝謝。

Answer 1

// Method to find lowest common ancestor. 
public Node lowestCommonAncestor(int val1, int val2,Node root){ 

    // Base condition to terminate. 
    if(root == null){ 
     return null; 
    } 

    // While traversing, if we found root itself equal to val1/val2. 
    // Then, root should be the lowest common ancestor. 
    if(root.data == val1 || root.data == val2){ 
     return root; 
    } 

    // If not, do post-order traversing. Means, left node, then right 
    // node, then root iteslf (current node.) 
    Node left = lowestCommonAncestor(val1, val2, root.left); 
    Node right = lowestCommonAncestor(val1, val2, root.right); 

    // While traversing, if we reach to a state, when root itself has left and 
    // right both children, then, this is the lowest common ancestor of val1, 
    // and val2. return this root. 
    if(left != null && right != null){ 
     return root; 
    } 

    // If, root has only one child either left or right child, then start 
    // traversing into that child. 
    // If, root has no child, in that case. Return null. Means this tree does  
    // not contain lowest common ancestor of val1, and val2. 
    return left != null ? left : right; 
} 

我通過發表評論來解釋整個代碼。我認爲這會更有意義。請通過它。如果您仍有疑問，請隨時提問。

Answer 2

這是一種純粹實施的樸素方法，但實現從上到下而不是標準的從下到上。讓我們試着分析lowestCommonAncestor(int val1, int val2,Node root)返回的內容。

left如果在root的左子樹中找到val1和val2中的至少一個，它將不爲空。在root的右側子樹中發現val1和val2中的至少一個，類似地正確將不爲空。顯然，如果聲明if(left != null && right != null){爲真當且僅當正是val1和val2一個在左子樹發現正是val1和val2一個在右子樹中找到。因此，這隻會發生在最低的共同祖先val1和val2（如果需要，請畫一張照片）。對於這個節點，根將返回。對於所有其他節點，函數將在左側或右側子樹中返回lowestCommonAncestor，具體取決於哪一個不爲空或者兩者都爲空。

所以對於LCA以上的所有節點，權正是一個離開會不會空（如val1和val2將在子樹之一），這將是該子樹，其中LCA是根。因此，對於LCA之上的所有節點，呼叫lowestCommonAncestor的返回值將是LCA本身。作爲一個conequence，原始樹根上的調用將是真正的LCA。