1650. Lowest Common Ancestor of a Binary Tree III - cocoder39/coco39_LC GitHub Wiki

1650. Lowest Common Ancestor of a Binary Tree III

Option 1: store the path

space complexity is O(m) where m is the longest path from p/q to root

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        path = set()
        cur = p
        while cur:
            path.add(cur)
            cur = cur.parent
        
        cur = q
        while cur:
            if cur in path:
                return cur
            cur = cur.parent
        return None

Option 2: 2 pointers

Time complexity is O(1)

same as intersection of 2 linked list 160. Intersection of Two Linked Lists (142. Linked List Cycle II). The difference is that here it is guaranteed that there is non-None intersection

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p1, q1 = p, q
        while p1 != q1:
            p1 = p1.parent if p1 else q
            q1 = q1.parent if q1 else p
        return p1