Как реализовать низшего общего предка для двоичного дерева с помощью 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; 
    } 
} 

Answer 1

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

Answer 2

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

если ток root node является нулевой то в текущем sub_tree там оленья кожа существовать common ancestor из р и д, поэтому вернуть null root==null

и если с или q - root. Я предполагаю, что р = корень и здесь, как для д, это либо offspring из р или not offspring из р, однако этого случая нет необходимости travese в sub_tree р, ибо, если в первом случае р является предок д так просто вернуть С. == корня, иначе возврат р напрямую, DonT ошибки производит, хотя в этом случае р не ancestor of q.
для справки
if(left != null && right != null) return root; , и я объясню это позже.

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

в настоящее время есть существует несколько возможных вещей:
1. р и д все offspring из root.left
2. Р- и Q все offspring корня. правый
3. эти два узла один - offspring из root.left другой - offspring of root.правая

---

эти два recursive statement используются, чтобы найти common ancestor из р и д (для 1,2) еще используется для поиска р и д (на 3)

---

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

это утверждение используется для обработки corresponding result из , р и д существуют left_subtree and right_suntree корня, так что ancestor является корень

---

return left != null ? left : right; 

это утверждение используется для процесс corresponding result от 1,2, p и q существуют одинаковые sub_tree либо влево, либо вправо.

Answer 3

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 является наименьшим общим знаменателем. IT остановится при первом запуске.

Если вы нарисуете себе двоичное дерево и протестируете каждый шаг, это будет иметь больший смысл.

Answer 4

Основная идея маркировки наличия ряда в ветви дерева является использование непустого указателя для числа НАЙДЕН и нулевого указателя для 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 return, так как ни один из них не будет найден.

---

По строковой линии пояснения.

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