LeetCode - 235. Lowest Common Ancestor of a Binary Search Tree

친구가 당근 개발자 면접을 앞두고 있어서 코딩테스트 준비를 함께하기로 했다. LeetCode는 코딩테스트를 준비할 수 있는 사이트다. 백준의 영어 버전이라고 보면 된다.

총 2주간 아래 링크의 75문제를 푸는 것이 목표이다. 무료로 공개되어 있기 때문에 누구나 해 볼 수 있다.

Grind 75 Questions 목록

Problem. Lowest Common Ancestor of a Binary Search Tree

Time limit: 30mins

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 Wikipedica: “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).”

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

Example

위와 같은 BST가 주어져 있을 때 test case와 정답은 다음과 같다.

#1 Test Case
Input: Root = 6, p = 5, q = 0
Output: 2

#2 Test Case:
Input: Root = 6, p = 8, q = 7
Output: 8

문제 파헤쳐 보기

문제의 상황은 다음과 같다.
Binary Search Tree(BST)의 서로 다른 두 노드의 공통 조상 중 가장 깊이 있는 조상을 찾는 것이다. 이를 최소공통조상이라고 하자.

알아야 하는 내용:

Binary Search Tree, 이진 탐색 트리

이진탐색트리(BST)는 트리 자료구조의 일종으로 다음과 같은 성질을 만족한다.

• 각 노드의 왼쪽 서브트리(subtree)에는 해당 노드의 값보다 작은 값을 지닌 노드들로만 구성되어 있다.
• 각 노드의 오른쪽 서브트리(subtree)에는 해당 노드의 값보다 작은 값을 지닌 노드들로만 구성되어 있다.

위의 성질을 만족하는 이진트리를 이진탐색트리(BST)라고 한다.

풀이법

주어진 두 노드의 위치부터 파악하기 위해, BST의 탐색 알고리즘을 적용한다. 이 과정에서 두 노드까지의 이동경로를 기록한다. 두 노드까지의 이동경로가 처음에는 같지만, 최소 공통 조상을 기점으로 두 경로가 달라지게 될 것이다. 즉, 각각의 노드로의 경로를 비교하여 처음으로 차이가 발생하는 지점이 최소 공통 조상의 위치이다.

#1 Test Case
Input: Root = 6, p = 5, q = 0
Output: 2

위의 테스트 케이스 1번을 예시로 살펴보자.
Root에서 p까지의 경로를 p_path, q까지의 경로를 q_path라고 하자.
p_path = (left, right, right, right), q_path = (left, left) 이다.
두 경로가 초반에는 left로 동일하다가, 최소 공통 조상인 2를 기점으로 달라지게 된다는 것이 확인 가능하다.
다만 주의할 것은 p 또는 q가 공통 조상이 되는 경우이다. 이 경우 한 경로가 나머지 경로를 완전히 포함한다.

정답 코드

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


class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        #Lets Store the path as a List type.
        p_path = []
        q_path = []
        
        #p_path
        #left -> 'l'
        #right -> 'r'
        x = root
        while(x != None and x.val != p.val):
            if x.val > p.val:
                x = x.left
                p_path.append('l')
            elif x.val < p.val:
                x = x.right
                p_path.append('r')
            else:
                break
        
        #q_path
        #left -> 'l'
        #right -> 'r'
        x = root
        while(x != None and x.val != q.val):
            if x.val > q.val:
                x = x.left
                q_path.append('l')
            elif x.val < q.val:
                x = x.right
                q_path.append('r')
            else:
                break
		
        
        n = len(p_path)
        m = len(q_path)
        ans = root
        count = 0
        for i in range(min(n, m)):
            if p_path[i] == q_path[i]:
                if p_path[i]=='l':
                    ans = ans.left
                else:
                    ans = ans.right
            else:
                return ans #Difference occured: Lowest Common Ancestor
        return ans 

시간복잡도

내가 고안한 풀이의 시간 복잡도에 대해 생각해보자. N개의 노드로 이루어진 BST라고 가정하자. 랜덤하게 BST가 만들어져 singly linked list 형태가 아니라고 한다면 p_path, q_path를 찾는 시간복잡도는 O(ln N)이다. 또한 두 path의 길이는 height인 ln N보다 작기 때문에 for문의 경우 O(ln N)의 시간복잡도를 갖는다. 따라서 전체의 시간복잡도는 O(ln N)이다.

Best Solutions

더 빠른 방법으로 문제해결이 가능할까?
나와 생각의 흐름은 동일하지만 훨씬 더 깔끔한 코드가 있었다. First draft와 같이 지저분한 코드보다는 앞으로 이런 최적화된 풀이를 쓸 수 있도록 연습해야겠다.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        temp = root 

        while temp:
            if p.val > temp.val and q.val > temp.val:
                temp = temp.right
            elif p.val < temp.val and q.val < temp.val:
                temp = temp.left
            else:
                return temp