leetcode 108. Convert Sorted Array to Binary Search Tree 정렬된 배열의 이진 탐색 트리 변환 문제풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

입력: 정렬되어 있는 배열

출력: 이진탐색트리

 

문제 요약: 문제 제목 그대로 정렬되어 있는 배열을 입력하면, 이진 탐색 트리 형태의 트리 노드를 출력하는 코드를 작성할 것

유의 사항: 먼저 이진탐색트리가 무엇인지를 알아야 한다.

 

이진 탐색 트리 (Binary Search Tree)란

이진트리 (자식 노드가 2개인 트리) 인데, 왼쪽 서브 트리는 현재 노드보다 작은 값, 오른쪽 서브 트리는 현재 노드보다 큰 값으로 구성된 트리

이진탐색트리 (출처: https://laptrinhx.com/binary-search-trees-through-javascript-245917333/)

속성:

중복 노드가 없다

서브 트리들 또한 이진 탐색 트리이다.

순회할 때는 inorder 방식이다. (왼쪽 서브 트리 -> 노드 -> 오른쪽 서브 트리) 

 

참고: https://velog.io/@hanrimjo/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree-8gk6ablvfx

생각 과정

입력이 [-10,-3,0,5,9] 라면, 당연히 가운데 있는 0이 rootnode가 될 것이다.

그리고 [-10, -3] 이 왼쪽 서브트리

[5, 9]이 오른쪽 서브 트리가 될 것이다.

이진트리이기 때문에 각각의 서브트리도 한 단계 더 깊어져야 하는데, 이것도 똑같이 이진 탐색 트리.

즉, 재귀로 풀 수 있을 것 같다. 

 

풀이

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

            
            mid=(left+right+1)//2
            
            root=TreeNode(nums[mid])
            
            root.left=dfs(left, mid-1)
            root.right=dfs(mid+1, right)
            
            return root
        
        return dfs(0, len(nums)-1)