java - How to implement lowest common ancestor for a binary tree using Java?

Question

I encountered the following implementation and spent some time, but still can't grasp the idea. Could someone please explain line by line what it is doing? I just don't understand at what point it can decide a node is an ancestor.

Thank you

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;
    }
}

score 3 · Accepted Answer

标记树分支中存在数字的基本思想是对数字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

在这种情况下，这将满足if(root == null || root == p || root == q) return root;

3.）它们中的任何一个都不存在于树中。这种情况不会被发现。如案例#2 所示，该函数立即返回，无需进一步遍历并在其下方的树中查找其对应项。

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;
}

score 1 · Accepted Answer

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;
}

score 0 · Accepted Answer

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

如果 currentroot node为null那么在当前 sub_tree 不存在p和qcommon ancestor，所以返回null root==null

如果p或q等于root。我假设p=root在这里对于q，它是 p或poffspring的，但是在这种情况下，不需要遍历 p 的子树，因为如果前一种情况p是q的祖先，那么只需返回pp ==root，否则直接返回p，虽然在这种情况下p不是，但它不会产生错误。对于声明，我稍后会解释。not offspringancestor of 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 都是offspringroot.left
2. p 和 q 都是offspringroot.right
3.这两个节点一个是offspringroot.left 另一个是offspringroot.right

这两个recursive statement用于查找p 和 q （common ancestor对于1,2） else用于查找p和q （对于 3）

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

该语句用于处理3corresponding result的，p 和 q 存在root 的，root也是left_subtree and right_suntreeancestor

 return left != null ? left : right;

该语句用于处理corresponding result1,2 ， p 和q存在相同的子树左侧或右侧。

score 0 · Accepted Answer

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 低于 root，但 4 不是，所以 2 是最小公分母。IT 将在第一次运行时停止。

如果你自己画一棵二叉树并测试每一步，它会更有意义。

java - How to implement lowest common ancestor for a binary tree using Java?

4 回答 4

Related

Reference