[LeetCode] 108. Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Easy

7274385Add to ListShare

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

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.

---

문제 풀이

문제 접근

1. 주어지는 데이터의 크기는 10^4로 크게 시간제약이 없는 듯하다.
2. Binary 탐색을 사용해서 풀어야할 것같다. 
3. 이미 정렬이 되어져 있는 리스트가 있다는 것.
4. 이진 탐색으로 배열을 따라갔을때 노드들을 연결하려면 Pre-order 순회 방식을 사용해야한다.

풀이

1. 정렬되어 있는 리스트를 높이가 균형인 이진트리로 변형해야한다.
2. 트리 모양을 전체적으로 보았을때 부모노드는 항상 가운데 이다.
3. 2진 탐색 재귀 방법을 사용하여 원하는 값까지 같은 과정으로 탐색할 수 있다.
4. 답으로 제출할 노드를 연결하려면, Pre-order 순회를 사용해야한다.

소스코드

# 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 rec(l, r):
            if l > r: 
                return None
            mid = l + (r - l + 1) // 2
            
            temp = TreeNode(nums[mid])
            
            temp.left = rec(l, mid - 1)
            temp.right = rec(mid + 1, r)
            
            return temp
        
        root = rec(0, len(nums) - 1)
        return root