[LeetCode 해석 및 풀이] 235. Lowest Common Ancestor of a Binary Search Tree(이진 검색 트리의 최하위 공통 조상)

LeetCode 문제 해석 및 풀이 방법

문제 235. Lowest Common Ancestor of a Binary Search Tree(이진 검색 트리의 최하위 공통 조상)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

 

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

한글

BST(이진 검색 트리)가 주어지면 BST에서 주어진 두 노드 중 가장 낮은 공통 조상(LCA) 노드를 찾습니다.

 

Wikipedia의 LCA 정의 에 따르면: “최하위 공통 조상은 두 노드 p 와 q 사이에서 p 와 q 모두 자손으로 갖는 T 의 가 장 낮은 노드로 정의됩니다(노드가 자체의 자손이 되도록 허용함).”

 

제한조건

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

 

입출력 예

입력	출력
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8	6
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4	2
root = [2,1], p = 2, q = 1	2

 

해답 및 해설

파이썬 (Python)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        min_val = min(p.val, q.val)
        max_val = max(p.val, q.val)
        def findCommon(root):
            val = root.val
            if val <= max_val and val >= min_val:
                return root
            elif val > max_val:
                return findCommon(root.left)
            elif val < min_val:
                return findCommon(root.right)
        
        return findCommon(root)

 이진탐색트리는 자기의 왼쪽에는 자기보다 작은 숫자의 노드들이, 오른쪽에는 큰 숫자의 노드들이 있는 트리이다. 따라서 두 노드의 최하위 마지막 공통조상의 값은 두 노드 값의 사이에 있을 수 밖에 없다. 따라서 위부터 아래로 내려오면서 노드의 값이 주어진 노드값 사이에 있는 경우를 찾아주면 된다.