[파이썬 알고리즘 인터뷰][BST] 정렬된 배열의 이진 탐색 트리 변환

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

정렬된 리스트를 받아 균형 이진 검색 트리 만들기

 

책에서 구현된 코드

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None

        mid = len(nums) // 2

        # 분할 정복으로 이진 검색 결과 트리 구성
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid + 1:])

        return node

 

기억해야할 기법

• 중간값(이진탐색)에서의 범위
  
  • right를 len(nums) -> len(nums)는 인덱스에 포함되지 않음
  • 따라서 mid를 구할 때 나머지를 버림

 

내가 구현한 코드

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def dfs(left: int, right: int):
            if right == left:
                return TreeNode(nums[left])
            if right == left + 1:
                nw_node = TreeNode(nums[right])
                nw_node.left = dfs(left,left)
                return nw_node

            mid = math.ceil((left + right) / 2)
            root = TreeNode(nums[mid])
            root.left = dfs(left, mid-1)
            root.right = dfs(mid+1, right)

            return root
        if len(nums):
            return dfs(0, len(nums)-1)
        return None

• 이진 탐색시 right를 range에서 벗어난 값으로 설정하고, mid를 구할 때 나머지를 버리면 코드가 더 깔끔해지는 듯
• 책에서 구현한 알고리즘 처럼 남은 요소가 2개 이하일 때 if 처리 없어 가능한 로직 생각하기
• 그래도 매 재귀마다 list 복사가 없어서 그런지, 속도는 내가 구현한 코드가 약간 빠름