Tree: 235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

 

https://youtu.be/gs2LMfuOR9k?si=KNjrz6AwcGwSPR0P

 

# 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를 찾아야 되서, root 가 null 일리는 없음

        cur = root

        while cur: # cur 가 null 일때까지 도는데, 
            if p.val > cur.val and q.val > cur.val: # p, q 값이 둘다 현재 노드의 val 보다 크면, 오른쪽으로
                cur = cur.right

            elif p.val < cur.val and q.val < cur.val: # p, q 값이 둘다 현재 노드의 val 보다 작으면, 왼쪽으로
                cur = cur.left
            else: 
                # 이 경우는 
                # 두개가 현재를 기준으로 쪼개질수도 있고
                # 두개 중 하나가 cur 가 될 수도 있음, 즉 하나가 조상이고.. 다른 하나는 자손이 됨
                return cur # 현재가 공통 조상 임