[Leetcode/Python] Convert Sorted Array to Binary Search Tree

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

 

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order. (값의 중복이 없다는 의미)

Code:

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

    
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:        
        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
        
        if not nums: return None
        return dfs(0, len(nums)-1)

1. 숫자가 담긴 리스트가 주어졌을 때 이들을 활용해 이진탐색트리를 생성하는 과정입니다.

2. 중위순회(inorder)하여야 한다.

3. 정수 리스트는 오름차순 정렬되어 주어집니다.

4. 분할정복으로 dfs를 진행합니다.(def dfs)

 

위 코드는 그냥 외워두고 쓰는 게 좋을 것 같다.

 

참고

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

다른 풀이:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        root = TreeNode()   

        if not nums:
            return None
        
        mid_index = len(nums)//2
        root.val = nums[mid_index]
        
        root.left = self.sortedArrayToBST(nums[:mid_index])
        root.right = self.sortedArrayToBST(nums[mid_index+1:])

        return root

 

self는 꼭 있어야 한다. 클래스 Solution이 self이다. 그러니까 self.sortedArrayBST는 Solution.sortedArrayToBST를 이른다.

1. 이미 오름차순 정렬되어 있는 상태이므로, 중간 값을 뽑으면 실제로도 중앙값이다. 따라서 이를 val로 삼는다.

2. 그리고 이 중간의 인덱스를 기준으로 앞쪽의 범위와 뒤쪽의 범위로 나누어 각각을 왼쪽 트리, 오른쪽 트리로 삼는다.

3. 이때 재귀적으로 sortedArrayToBST에 위에서 나눈 리스트 두개를 각각 인자로 전달한다.

4. 위와 같은 방식으로 트리를 끝까지 생성하면 root를 리턴한다.

5. 넘겨 받은 인자가 없으면 None을 리턴한다.