最低共同祖先-代码解释

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)返回什么。

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

left不为空。类似地，当且仅当val1和val2中至少有一个在root的右子树中，right将不为空。显然，if语句if(left != null && right != null){将为真，当且仅当精确地 val1和val2中的一个在左子树中，精确地 val1和val2中的一个在右子树中。因此，这只会发生在val1和val2的最低共同祖先(如果需要，请绘制图片)。对于这个节点，将返回根节点。对于所有其他节点，该函数将返回左子树或右子树中的lowestCommonAncestor，具体取决于哪一个不为空，如果两个都为空，则返回null。

所以对于LCA上面的所有节点，右和左恰好有一个不为空(因为val1和val2将在一个子树中)，这将是LCA所在的子树的根。因此，对LCA之上的所有节点调用lowestCommonAncestor的返回值将是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;
}

我用注释解释了整个代码。我觉得这样更有意义。请过目一下。如有疑问，请提出来。