如何使用自下而上的递归在二叉树中找到最低的共同祖先

Question

我很难理解如何使用自下而上的递归在二叉树中找到最低的共同祖先。

这是看起来非常整洁的解决方案。我试着在一棵小树上干燥运行它，但没有运气。

有人可以帮忙吗？

Answer 1

如果链接发生变化，下面会重现您链接到的算法：

public static Tree findLowestCommonAncestor(Tree root, Tree p, Tree q)
{
    if (root == null)
        return null;
    if (root == p || root == q)
        return root;
    Tree left = findLowestCommonAncestor(root.left, p, q);
    Tree right = findLowestCommonAncestor(root.right, p, q);
    if (left != null && right != null)
        return root;
    if (left != null)
        return left;
    else
        return right;
}

它的工作原理是这样的。关键的观察结果是，如果我们考虑一个节点n是p和q的祖先，并询问它是否是最低的共同祖先，基本上有三种可能性：

1. P和Q都是N的左子代的后代，但不是右子项;
2. P和Q都是N的右子代的后代，但不是左子代;
3. P 和 q 都是 N 的两个子代的后代。

这就是整个算法背后的想法。我们从根源开始，然后向下工作。我们从当前节点的左子节点 l 和当前节点的右子 r 递归查找 p 和 q 的 LCA。

如果左手搜索

返回某些内容，但右手搜索没有，那么这意味着左手搜索找到了正确的值（因为答案低于当前节点，并且要么是 l 本身，要么是 l 的后代）。同样，如果右侧搜索返回某些内容，但左侧搜索没有。

如果左手和右手搜索都返回某些内容，则 p 和 q 都是 n 的后代。这意味着我们可以返回 n 作为 LCA：它不能更低，否则我们会在递归搜索中更早地找到它;而且它是一个共同的祖先，因此它必须是最低的祖先。

（顺便说一下，这种语言并不是特别有用：我会说你想要的祖先是树中最高的祖先，但在你所看到的中，最低似乎意味着最接近根。