0

我很容易实现和理解按顺序和后序遍历的 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;

有人可以解释一下吗？

谢谢你。

4

2 回答 2

2

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

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

因此，对于 LCA 上方的所有节点，恰好右侧和左侧之一将不为空（因为val1并将val2在其中一个子树中），这将是 LCA 所在子树的根。因此，lowestCommonAncestor对 LCA 之上的所有节点的调用的返回值将是 LCA 本身。因此，对原始树根的调用将真正成为 LCA。

于 2015-10-06T10:24:21.517 回答
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;
}

我通过添加注释来解释整个代码。我认为这会更有意义。请通过它。如果您仍有任何疑问，请随时提问。

于 2015-10-06T10:35:52.547 回答