如何使用自底向上递归在二叉树中找到最低公共祖先

Question

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

HERE 是看起来非常整洁的解决方案。我试着在一棵小树上晾干它，但没有成功。

有人可以帮忙解决这个问题吗？

Answer 1

您link编辑的算法复制如下，以防 link 发生变化：

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 的祖先，再问是不是最低共同祖先，基本有3种可能：

p 和 q 都是 n[=52= 的左 child 的后代]，但不是正确的 child;

p 和 q 都是 n[=52= 的右 child 的后代]，但不是左边 child;

p 和 q 都是 n[=52= 的 children 的后代].

这就是整个算法背后的思想。我们从根开始，一路往下。我们从左边child l递归地找到p和q的LCA当前节点，以及当前节点的右childr

如果 left-hand 搜索 return 有结果，但 right-hand 搜索没有，那么这意味着 left-hand 搜索找到了正确的值（因为答案低于当前节点，并且 l 本身或 l 的后代）。类似地，如果 right-hand 搜索 return，但 left-hand 搜索没有。

如果 left-hand 和 right-hand 都搜索 return 东西，那么 p 和 q 都是 n 的后代。这意味着我们可以 return n 作为 LCA：它不能更低，否则我们会在递归搜索中更早地找到它；而且是共同祖先，所以一定是最低的。

（语言不是特别有用，顺便说一句：我说过你想要的祖先是树中最高的，但在你正在看，lowest好像是最接近root的意思。）

如何使用自底向上递归在二叉树中找到最低公共祖先

How to find lowest common ancestor in binary tree using bottom up recursion

algorithm

recursion

binary-tree