[Leetcode 235] - Lowest Common Ancestor of a Binary Search Tree w/ Python

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).”

 

 

 

이진 탐색 트리와 2개의 노드가 주어진다. 최소 공통 조상을 찾아서 리턴

결국 두개의 노드에서 가장 가까운 공통 조상을 찾는 문제이다

 

 

 

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

 

 

---

 

 

 

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

 

 

 

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant 
of itself according to the LCA definition.

 

 

 

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

 

---

 

 

 

처음에는 문제를 잘못 이해해서 이 숫자들 중에서 가장 낮은 높이의 노드를 구하는 문제인줄 알았다 (크흠...)

문제를 이해한 다음에는 굉장히 쉬운 문제라고 생각했는데 왜 Medium 수준의 문제로 분류 됐는지...

 

일단 이진 "탐색" 트리 이기 때문에 Root 기준에서 왼쪽은 더 낮은 숫자, 오른쪽은 더 높은 숫자라는 것을 알 수 있다

 

이를 통해 주어진 가능성은 3개:

1. 두 숫자가 둘다 Root 보다 작으면 왼쪽 탐색

2. 반대로 크면 오른쪽 탐색

3. 왼쪽 오른쪽으로 나눠져 있으면 Root를 그냥 리턴하면 된다

 

 

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        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

 

 

굉장히 간단한 솔루션~