235, Lowest Common Ancestor of a Binary Search Tree

# 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':
    	"""가장 작은 부모 찾기
        
        경우의 수:
            * P, Q가 부모 노드 왼쪽에만 존재하는 경우
            * P, Q가 부모 노드 오른쪽에만 존재하는 경우
            * P는 부모 노드 왼쪽, Q는 부모 노드 오른쪽에 존재하는 경우
            * P 또는 Q 중 하나가 루트 노드에 존재하는 경우
        
        LCA, Lowest common ancestor
        
        Binary Tree: 
            * 노드의 자식노드는 2개
        Binary Search Tree: 
            * 노드의 자식노드는 2개
            * 왼쪽 노드는 부모 노드보다 작은 값만 존재
            * 오른쪽 노드는 부모 노드보다 큰 값만 존재
        
        Returns:
            메모리: 20.28MB
            런타임: 54ms
        """
        curr = root
        while curr:
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            else:
                # p.val <= curr.val <= q.val
                # LCA
                return curr

 

[참고 글]