1650. Lowest Common Ancestor of a Binary Tree III (Hash Table, Two Pointers, Tree, Binary Tree)

링크 - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Find q in p's children, and find common ancestor

이 방법은 먼저 q가 p의 children node들 중에 있다는 가정부터 시작한다. 여기서는 dfs를 통해 이 값을 찾아낸다. 만약 존재한다면 p를 반환하면 된다.

q가 p의 children node들 중에 없다면, 다음 방법으로는 p와 q의 조상들을 비교해야한다. 따라서 먼저 p의 조상들을 set()에 집어넣고, q의 조상들을 비교하며 가장 먼저 만나는 조상을 반환해야 한다.

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        # Find if there is q in childe nodes of p
        def helper(node):
            if not node:
                return False

            if node == q:
                return True

            return helper(node.left) or helper(node.right)
        q_exist = helper(p)
        if q_exist:
            return p

        # If not, store parents of p, then compare parents of q
        ancestors = set()
        while p:
            ancestors.add(p)
            p = p.parent

        while q not in ancestors:
            q = q.parent
        return q

Time Complexity: O(n) 

Space Complexity: O(n) dfs stack, ancestors를 보관할 set()

2) O(1) space complexity

이 방법은 p와 q를 각각의 다른 포인터에 넣은뒤, 포인터들의 parent를 찾아가고 null이 나오면(root 도달) q와 p로 바꿔서 계속 반복하는 식이다. 이러다 보면 언젠가는 ancestor에 만나게 되고 이것이 우리가 찾는 LCA다.

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

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

Time Complexity: O(n)

Space Complexity: O(1)