最低公共祖先 - 代码说明

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。