最低共同祖先-代码解释

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

这是（某种）朴素方法的巧妙实现，但实现的是自上而下而不是标准的自下而上。让我们试着分析一下 lowestCommonAncestor(int val1, int val2,Node root) return.

如果在 root 的左子树中找到 val1 和 val2 中的至少一个，

left 将不为空。类似地，当且仅当在 root 的右子树中找到 val1 和 val2 中的至少一个时，right 才不会为空。显然，当且仅当恰好在左子树中找到 val1 和 val2 之一并且 [=35] 时，if 语句 if(left != null && right != null){ 才为真=]恰好在右子树中找到val1和val2之一。因此，这只会发生在 val1 和 val2 的最低共同祖先（如果需要，请画图）。对于此节点，根节点将 returned。对于所有其他节点，该函数将 return 左子树或右子树中的 lowestCommonAncestor 取决于哪个不为空或如果两者都为空则为空。

所以对于 LCA 以上的所有节点，恰好右和左之一将不为空（因为 val1 和 val2 将在其中一个子树中）并且这将是根LCA所在的子树。因此，对于 LCA 之上的所有节点，调用 lowestCommonAncestor 的 return 值将是 LCA 本身。因此，对原始树根的调用实际上就是 LCA。

Answer 2

// 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;
}

我通过注释解释了整个代码。我认为这会更有意义。请通过它。如果您还有疑问，请随时提问。

最低共同祖先-代码解释

Lowest Common Ancestor- Code Explain

algorithm

binary-tree

lowest-common-ancestor