[알고리즘] Lowest Common Ancestor of a Binary Search Tree

포인트

• LCA 공통 조상 문제를 이진 탐색 문제에서 어떻게 해결할 수 있는가? 를 물어보는 문제 입니다. 반복문과 재귀 2가지 방향으로 풀이를 할 수 있습니다.
• 개인적으로 반복문의 형태가 이해하기 편하다고 생각합니다. 기준 노드들 전부보다 크다면 오른쪽 노드를 다시 확인 전부 작다면 왼쪽 노드를 다시 확인 그렇지 않을 경우 그 노드가 최소 공통의 조상 노드가 됩니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

# 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':
        while root:
            # 노드가 유효할 때까지 반복을 합니다.
            if root.val > p.val and root.val > q.val:
                root = root.left
                # 노드가 기준 노드 들보다 값이 큰 경우 왼쪽으로 

            elif root.val < p.val and root.val < q.val:
                root = root.right
                # 노드가 기준 노드 들보다 값이 작은 경우 오른쪽으로
            else:
                break
                # break
        return root

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: 
            return None

        if p.val>root.val and q.val>root.val: 
            return self.lowestCommonAncestor(root.right, p, q)

        if p.val<root.val and q.val<root.val: 
            return self.lowestCommonAncestor(root.left, p, q)
            
        return root