Today's Challenge

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

Lowest Common Ancestor of a Binary Tree - LeetCode

오랫만에 트리 구조의 문제

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        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