# LeetCode Easy 108. Convert Sorted Array to Binary Search Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

昇順にソート済みの配列が与えられた時，高さのバランスが取れたBSTに変換しろという問題です．

ソートした配列の中心の値よりも，右側は大きく，左側は小さいということを利用してやります．

解法

• 配列の中心を親として，左側が左部分木，右側が右部分木になります．
• そして，再帰的に左側の配列の中央の値左部分木の親とし，右側の配列の中央の値右部分木の親とします．

計算量

配列の大きさを$N$とし，出来上がる木の深さを$H$とします．

• 時間計算量
  • 全ての配列を走査するので$O(N)$
• 空間計算量
  • $O(H)$

Python

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

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if nums == []:
            return None
        def convert_sorted_array_into_bst(nums: int, low: int, high: int) -> TreeNode:
            if low > high:
                return None
            mid = low + (high - low) // 2
            mid_node = TreeNode(nums[mid])
            mid_node.left = convert_sorted_array_into_bst(nums, low, mid-1)
            mid_node.right = convert_sorted_array_into_bst(nums, mid+1, high)
            return mid_node
        return convert_sorted_array_into_bst(nums, 0, len(nums)-1)