236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Lowest Common Ancestor of a Binary Tree - LeetCode

Solution

class Solution:
    def __init__(self):
        self.ans = None
        
    def lowestCommonAncestor(self, root, p, q) :
        ans = None
        def recur(node):
            if self.ans or node is None:
                return False
            
            ll = recur(node.left)
            rr = recur(node.right)

            if node.val == p.val or node.val == q.val:
                if ll or rr:
                    self.ans = node
                    return False
                else:
                    return True

            if ll and rr:
                self.ans = node
                return False
            if ll or rr:
                return True

            return False
        
        recur(root)
        return self.ans

• 함수 안에서 같은 ans를 비교하고 변환시키기 위해서 __init__에 self 변수로 선언한다.
• 재귀함수를 사용했다.
• 이미 ans가 나왔거나 인자로 받은 노드가 None이면 False를 반환한다.
• 양쪽 자식의 결과를 가져온다.
• 나 자신이 p 또는 q 라면 자식 중 하나라도 True일 때 ans를 설정하고 False를 반환한다.
• 자식 중 하나라도 없으면 True를 반환해서 위로 전달한다.
• 나 자신이 p 또는 q가 아니라면 자식 모두 True일 때 ans를 설정하고 False를 반환한다.
• 자식 중 하나만 True라면 그대로 반환해서 위로 전달한다.
• 자신도 자식도 True가 없다면 False를 반환한다.

Another 1

class Solution:
    def __init__(self):
        self.ans = None

    def lowestCommonAncestor(self, root, p, q):
        def recur(node):
            if not node:
                return False
                
            left = recur(node.left)
            right = recur(node.right)
            mid = node == p or node == q

            if mid + left + right == 2:
                self.ans = node

            return mid or left or right
            
        recur(root)
        return self.ans

• 나와 같은 방법을 더 심플하게 구현했다.
• 양쪽 자식과 나, 셋 중에 2개가 True라면 ans를 저장한다.
• 그게 아니라면 or 를 통해 True or False를 전달한다.

Another 2

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        stack = [root]
        parent = {root: None}

        while p not in parent or q not in parent:
            node = stack.pop()

            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        ancestors = set()

        while p:
            ancestors.add(p)
            p = parent[p]

        while q not in ancestors:
            q = parent[q]
        return q

• stack을 사용해서 BFS로 노드를 확인한다.
• parent에는 key:자식, value:부모 를 넣는다.
• while문은 parent에 p와 q가 모두 들어올 때까지 반복한다.
• while문 이후 p 노드를 시작으로 parent를 사용하여 root 노드까지의 부모들을 ancestors에 넣는다.
• q에서 다시 올라가면서 ancestor에 있는 노드가 나오면, p와 q가 모두 가지고 있는 첫 부모이므로 반환한다.