0108. Convert Sorted Array to Binary Search Tree - chasel2361/leetcode GitHub Wiki

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

這題要求將排序過的陣列轉換成高度平衡的二元搜尋樹，若要達成高度平衡，根就必須選擇中位數，左右子樹的根也必須為其範圍內的中位數

[1] 如果個數為偶數，中位數就取中間兩個數較小者
[2] 左子樹的選取範圍從 l 到 m - 1
[3] 右子樹的選取範圍從 m + 1 到 r
[4] 如果 l > r 表示到盡頭了

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums or len(nums) == 0: return None
        return self.getNode(0, len(nums) - 1, nums)
        
    def getNode(self, l, r, nums):
        if l > r: return None  # [4]
        m = (l + r) // 2  # [1]
        root = TreeNode(nums[m])
        root.left = self.getNode(l, m - 1, nums)  # [2]
        root.right = self.getNode(m + 1, r, nums)  # [3]
        return root

這樣寫的時間複雜度為 O(N)，空間複雜度因遞迴的關係為 O(N)