108. Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree - LeetCode

1. DFS

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def dfs(cur_list):
            if not cur_list:
                return None
            mid = len(cur_list) // 2
            cur_node = TreeNode(cur_list[mid])
            cur_node.right = dfs(cur_list[mid + 1:])
            cur_node.left = dfs(cur_list[:mid])
            return cur_node

        return dfs(nums)

오름차순 정렬된 리스트가 주어지면 BST를 만드는 문제다.

여기서 포인트는 BST의 모든 노드의 왼쪽, 오른쪽 서브 트리의 높이가 1보다 같거나 작게 만드는 것이 조건이다.

트리의 HEAD에 해당하는 TreeNode 객체를 반환해야 하기 때문에 DFS 탐색을 하면서 TreeNode를 만들어줘야 한다.

 

모든 노드의 왼쪽, 오른쪽 서브 트리의 높이를 1보다 같거나 작게 만든다는 것은,

왼쪽, 오른쪽 서브 트리에 할당해주는 노드 개수의 차이가 0이나 1이면 된다.

다시 말해서 중간 인덱스에 해당하는 값을 중심으로 트리를 만들어 나가면 된다.

 

[-10,-3,0,5,9]라는 배열로 시작하면

 

i. 중간 인덱스인 0이 이 트리의 ROOT가 된다

ii. 현재 배열을 중간 인덱스를 중심으로 나눈다. 그럼 왼쪽은 [-10, 3], 오른쪽은 [5, 9]로 나뉜다.

iii. 나눠진 배열을 이용해서 위 과정을 반복하고 양쪽 서브 트리의 ROOT가 되는 노드를 반환한다.

iv. 반환받은 노드를 트리의 ROOT 왼쪽, 오른쪽에 할당해준다.

 

예전보단 재귀와 친해진 것 같다.