236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

DFT / BFT 랑 queue 를 이용하는 식으로 생각함 pop 해서 와짜구자짜구..
p 의 ancestors 와 q 의 ancestors 를 찾아서 둘이 겹치는 ancestor 를 찾으려했으나... 안됨;

Iterative using parent pointers

Solution 1: Runtime: 68 ms - 83.66% / Memory Usage: 18.1 MB - 93.60%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Stack for tree traversal
        stack = [root]

        # Dictionary for parent pointers
        parent = {root: None}

        # Iterate until we find both the nodes p and q
        while p not in parent or q not in parent:

            node = stack.pop()

            # While traversing the tree, keep saving the parent pointers.
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        # Ancestors set() for node p.
        ancestors = set()

        # Process all ancestors for node p using parent pointers.
        while p:
            ancestors.add(p)
            p = parent[p]

        # The first ancestor of q which appears in
        # p's ancestor set() is their lowest common ancestor.
        while q not in ancestors:
            q = parent[q]
        return q

딕셔너리를 이용해서 parent ..

이해가 안돼요ㅠㅠ

트리 트라우마.. ㅌㄹ ㅌㄹㅇㅁ..

Recursion

Solution 2: Runtime: 68 ms - 83.66% / Memory Usage: 25.3 MB - 56.45%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # I have reached a dead end, I didn't find anything here
        if not root:
            return None
        
        # I see one of the targets! I will inform my caller!
        if root == q or root == p: return root
        
        # Look in the left, if you find p or q , return yourself
        foundInLeft = self.lowestCommonAncestor(root.left, p, q)
        
        # Look in the right, if you find p or q , return yourself
        foundInRight = self.lowestCommonAncestor(root.right, p, q)
        
        # Didnt find anything in the left, must be in right
        if not foundInLeft: return foundInRight
        
        # Didnt find anything in the right, must be in the left
        if not foundInRight: return foundInLeft
        
        # Found something in both! Hence this is the one!
        return root

뭔가 이게 이해하기는 더 좋아보이는데...

완전 이해는 안된다는 점..^^