如何使用Java实现二叉树的最近公共祖先？

Question

我遇到了以下的实现方式，花了一些时间，但仍然无法掌握其思想。请问是否有人能够逐行解释它在做什么？我不明白在何时可以确定一个节点是祖先。

谢谢

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}

- user2426823

---

递归函数可能很棘手，难以理解。在纸上画出它们可以帮助理解。 - Saurav Sahu

这里的代码是一个稍微紧凑一些的版本，与此答案中的代码有所不同：https://dev59.com/t3M_5IYBdhLWcg3wMgAF#9046307 - Hulk

@ Hulk，不要误会，这个差异对于编译器来说完全无关紧要。 - Saurav Sahu

@SauravSahu 是的，我同意它们是等价的。区别仅在于风格和注释。 - Hulk

Answer 1

在树枝中标记数字存在的基本思想是使用非空指针表示找到的数字FOUND，使用空指针表示NOTFOUND。一旦找到数字(p或q)或root为null，调用堆栈就会回溯。后者清楚地表明没有搜寻到该数字。

有四种可能的情况: 1.) 两个数字在同一父节点下。

                      root
                      /  \ 
            Leftsubtree  Rightsubtree
                p/q        q/p

在这个例子中，在下面的代码中，当满足以下条件时（if(left != null && right != null)），就会出现一个时刻：返回根节点（return root;）。

2.) 一个父节点是另一个父节点的上级。

      q/p                     p/q
      /            OR          \ 
Leftsubtree                 Rightsubtree
  p/q                           q/p

在这种情况下，如果根节点为null或等于p或q，则会满足if(root == null || root == p || root == q) return root; 3.) 如果它们两者都不在树中，那么这个条件将被忽略。如第二种情况所示，函数立即返回而不进一步遍历并查找其在树下的对应项。

4.) 它们两者都不在树中。

对于每个不存在的子节点，第一行代码if(root == null ... return ;都将被执行。最终结果将返回null，因为没有任何数字会被找到。

逐行解释代码。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q)  return root;

    /* (root == null)  This proves that root is not in the branch of tree of our interest. Returning null would means NOTFOUND.*/
    /* (root == p || root == q) either p or q or both are found. Returning non-null root would means FOUND. */

    /*Check for presence in leftsubtree */
    TreeNode left = lowestCommonAncestor(root.left, p, q);

    /*Check for presence in rightsubtree */
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    /*            root
                  /  \ 
        leftsubtree  Rightsubtree
            p/q        q/p

    */
    if(left != null && right != null)   return root; //both the numbers are found inside tree under root 

    // left or right subtree OR both don't have p or q. Return the overall find result under root.
    return left != null ? left : right;
}

- Saurav Sahu

Answer 2

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // root == null (no root no LCA)
    // root == p || root == q (if either p or q is the root then root is LCA)
    if(root == null || root == p || root == q)  return root;
    //get the LCA of p and q in left sub tree
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    //get the LCA of p and q in right sub tree
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // if one of p or q is in left subtree and another is in the right subtree, 
    //then the root is the LCA
    if(left != null && right != null)   return root;
    // if left is not null, left is LCA, else right is LCA 
    return left != null ? left : right;
}

- shawn

---

https://dev59.com/t3M_5IYBdhLWcg3wMgAF - shawn

Answer 3

if(root == null || root == p || root == q)  return root;

如果当前的根节点为null，则在当前的子树中不存在p和q的共同祖先，因此返回null root==null。

如果p或q等于root。我假设p=root，至于q，它要么是p的后代，要么不是p的后代，但无论哪种情况，都无需遍历p的子树，因为如果前一种情况下p是q的祖先，那么只需返回p p==root，否则直接返回p，即使在这种情况下p不是q的祖先也不会产生错误。
对于语句
if(left != null && right != null) return root; 我稍后会解释。

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

现在有几种可能性：
1. p 和 q 都是 root.left 的 offspring
2. p 和 q 都是 root.right 的 offspring
3. 这两个节点一个是 root.left 的 offspring，另一个是 root.right 的 offspring

---

这两个 递归语句 用于查找p和q的共同祖先 (1,2情况) 否则用于查找p和q (3情况)

---

if(left != null && right != null)   return root;

这个语句用于处理3的相应结果，p和q存在于根节点的左子树和右子树中，因此祖先是根节点

---

 return left != null ? left : right;

这个语句用于处理1,2的相应结果，p和q存在相同的子树，无论是左边还是右边。

- nail fei

---

这是第一个直接回答“请逐行解释此LCA实现在做什么”的答案。它可以明确指出，对于“外部”使用，它“假定”_p_和_q_都在_root_中的树上，而在“内部”/递归使用中，它“依赖于”这种情况并非总是如此，这暴露了_common_在lowestCommonAncestor()中的常见性质。让我指出，问题中提出的“解决方案”缺乏文档注释和内联注释。 - greybeard

Answer 4

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root->val == p->val || root->val == q->val ||
        (p->val < root->val && root->val < q->val) ||
        (q->val < root->val && root->val < p->val)) {
        return root;
        }
    else if (root->val < p->val) return lowestCommonAncestor(root-> right, p, q);
    else return lowestCommonAncestor(root->left, p, q);

这是我的C++答案，但只要将“->”切换为“.”语法，它应该非常相似。这是一个递归函数，它检查当前叶子节点及其左右子节点，一旦第一个if语句的条件为真，就意味着它已经确定了最低公共祖先，因为如果它的任何一个子节点更大，那么它就是最小值。

例如：给定2作为根节点，1和4作为其子节点（分别为左和右），1小于根节点，但4不是，因此2是最小公共分母。它会在第一次运行时停止。

如果您自己绘制二叉树并测试每个步骤，它将更加清晰明了。

- johnson