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 # 현재가 공통 조상 임

 

# 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':
        # BST에서 공통 부모 찾기
        cur = root

        while cur: # 노드 끝가지 가서 None 되면 멈춤
            if cur.val < p.val and cur.val < q.val: # p,q 둘다 오른쪽에 있으면
                cur = cur.right
            elif cur.val > p.val and cur.val > q.val: # p,q 둘다 왼쪽에 있으면
                cur = cur.left
            else: # 두개가 각각 양쪽에 있으면, cur 가 공동조상임
                return cur

 

# 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':
        # 가장 "낮은" 공통 조상 찾기
        if not root:
            return root # None

        cur = root
        while cur:
            # 자식이 둘다 현재 노드보다 오른쪽에 있으면, 오른쪽으로 내려가고
            if cur.val < p.val and cur.val < q.val:
                cur = cur.right
            # 자식이 둘다 현재 노드보다 왼쪽에 있으면, 왼쪽으로 내려가고
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else: # 자식이 양쪽에 있으면. 현재 내가 공통 조상임
                return cur

        # 끝까지 다 돌았는데, 조상이 없으면
        return None