leetcode with python:108. Convert Sorted Array to Binary Sea

题目:

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.

给定一个sorted list,将它转变成高度平衡二元树(height-balanced binary tree)
高度平衡二元树定义:所有两子树高度最多相差1的binary tree
ex:input:[-10,-3,0,5,9]=>output: [0,-3,9,-10,null,5]or[0,-10,5,null,-3,null,9]

按照题目给的範例,可以看出规律是取mid当root,分开的两串阵列再取mid当左右节点,以此类推
我们按照这样的理念实作程式

# 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 = rightclass Solution:    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:        if len(nums)==0: #当没东西时回传None,不开新节点            return None                    if len(nums)==1: #当值只有一个时,就开此值的节点就好            return TreeNode(nums[0])                    mid=len(nums)//2        root=TreeNode(nums[mid])        root.right=self.sortedArrayToBST(nums[mid+1:len(nums)])        root.left=self.sortedArrayToBST(nums[0:mid])        return root

先开一个值为nums[mid]的节点
mid两边的list用一样的手法递迴不断往下开左右节点,直到list被切割到长度只剩0或1为止
最后执行时间63ms(faster than 93.48%)

那我们下题见