[Neetcode/Tree] Lowest Common Ancestor in Binary Search Tree

https://neetcode.io/problems/lowest-common-ancestor-in-binary-search-tree

NeetCode

공통 조상 찾기!

🔹 BST(Binary Search Tree)의 특징 활용

BST(이진탐색트리)에서는 왼쪽 서브트리의 모든 값이 루트보다 작고, 오른쪽 서브트리의 모든 값이 루트보다 큽니다.
따라서, LCA를 찾는 과정에서 다음 규칙을 사용할 수 있습니다.

1. p.val과 q.val이 모두 현재 노드보다 작으면, LCA는 왼쪽 서브트리에 있음.
2. p.val과 q.val이 모두 현재 노드보다 크면, LCA는 오른쪽 서브트리에 있음.
3. p.val과 q.val이 현재 노드 양쪽에 걸쳐 있다면, 현재 노드가 LCA임.

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

🔹 설명 ( 재귀 - Recursive)

• 왼쪽으로 내려가야 하는 경우: p와 q가 모두 현재 노드보다 작을 때 → root.left에서 LCA 탐색
• 오른쪽으로 내려가야 하는 경우: p와 q가 모두 현재 노드보다 클 때 → root.right에서 LCA 탐색
• 현재 노드가 LCA일 경우: p와 q가 현재 노드의 양쪽에 위치하면 현재 노드가 LCA