Skip to content

1650. Lowest Common Ancestor of a Binary Tree III 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  // Same as 160. Intersection of Two Linked Lists
  Node* lowestCommonAncestor(Node* p, Node* q) {
    Node* a = p;
    Node* b = q;

    while (a != b) {
      a = a == nullptr ? q : a->parent;
      b = b == nullptr ? p : b->parent;
    }

    return a;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  // Same as 160. Intersection of Two Linked Lists
  public Node lowestCommonAncestor(Node p, Node q) {
    Node a = p;
    Node b = q;

    while (a != b) {
      a = a == null ? q : a.parent;
      b = b == null ? p : b.parent;
    }

    return a;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  # Same as 160. Intersection of Two Linked Lists
  def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
    a = p
    b = q

    while a != b:
      a = a.parent if a else q
      b = b.parent if b else p

    return a