[leetcode]108. Convert Sorted Ar

题目

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:

      0
     / \
   -3   9
   /   /
 -10  5

分析

这道题目的是将有序序列转化为二叉平衡树。首先，找到序列的居中元素作为头节点。 该节点的左侧元素全部属于左子树， 右侧元素全部属于右子树。递归边界是序列中所有元素都放到平衡树中。
代码如下：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return
        return self.createBST(nums, 0, len(nums)-1)
    
    def createBST(self,array: List[int], start: int, end: int ):
        if start > end: # 当所有元素放入树中
            return
        mid = (start + end) // 2  # 结果向下取整
        head = TreeNode(array[mid])
        
        head.left = self.createBST(array, start, mid-1)
        head.right = self.createBST(array, mid+1, end)
        return head

简化

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