[Leetcode] 235. Lowest Common Ancestor of a Binary Search Tree_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '235. Lowest Common Ancestor of a Binary Search Tree'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. ' Lowest Common Ancestor of a Binary Search Tree' 알고리즘 문제

 

STEP 2. ' Lowest Common Ancestor of a Binary Search Tree' 코드(code)

 

STEP 3. ' Lowest Common Ancestor of a Binary Search Tree' 해설

 

STEP 4. ' Lowest Common Ancestor of a Binary Search Tree' solution

 

반응형

 

STEP 1. ' Lowest Common Ancestor of a Binary Search Tree' 알고리즘 문제

 

Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

 

모든 노드의 값이 고유한 이진 탐색 트리(BST)와, 그 트리 내에 존재하는 두 노드 p와 q가 주어졌을 때, 두 노드의 최소 공통 조상 (LCA: Lowest Common Ancestor)을 반환하세요.

최소 공통 조상은 두 노드 p와 q의 가장 낮은 공통 조상 노드를 의미하며, 조상 노드는 자기 자신을 포함할 수 있습니다.

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

 

---

STEP 2. ' Lowest Common Ancestor of a Binary Search Tree' 코드(code)

 

■ Runtime: 45ms Beats 98.38%
■ Memory: 21.20MB Beats 20.45%

 

# 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':

        currentNode = root

        while currentNode:
            currentVal = currentNode.val
            pVal = p.val
            qVal = q.val

            if pVal < currentVal and qVal < currentVal:
                currentNode = currentNode.left
            elif pVal > currentVal and qVal > currentVal:
                currentNode = currentNode.right
            else:
                return currentNode

---

STEP 3. ' Lowest Common Ancestor of a Binary Search Tree' 해설

 

이진 탐색 트리(BST)는 왼쪽 자식 < 부모 노드 < 오른쪽 자식 구조를 가지므로, 노드 p와 q의 위치에 따라 다음 세 가지 경우로 나뉩니다:

 

1. p와 q의 값이 모두 현재 노드보다 작다면 → 왼쪽 서브트리로 이동
2. p와 q의 값이 모두 현재 노드보다 크다면 → 오른쪽 서브트리로 이동
3. 한 노드는 작고, 다른 하나는 크거나 같은 경우 → 현재 노드가 최소 공통 조상이므로 반환

 

이러한 조건을 바탕으로 현재 노드를 기준으로 p와 q가 어느 방향에 있는지 비교하면서 탐색을 진행하고, 공통 조상이 되는 노드를 찾아 반환합니다.

 

 

STEP 4. ' Lowest Common Ancestor of a Binary Search Tree' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 58ms Beats 60.89%
■ Memory: 21.01MB Beats 48.29%

 

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

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '235. Lowest Common Ancestor of a Binary Search Tree'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.