108. Convert Sorted Array to Binary Search [Python]
108. Convert Sorted Array to Binary Search
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.
给定一个升序的矩阵,将它转换成一棵平衡二叉树。
其中,平衡二叉树是指树中每个节点子树高度差的绝对值不超过1的树。
思路:由于左右高度差的绝对值不能超过1,所以树根节点应选择升序列表中间的元素,即nums[len(nums)//2]。
该元素前面的元素(比根节点小的元素)同理递归地放入左子树;后面的元素递归地放入右子树。
最后返回各个节点。
代码
class Solution: def sortedArrayToBST(self, nums): """ @param type nums: List[int] @param rtype: TreeNode """ if nums == None: return if len(nums) == 1: return nums[0] root = nums[len(nums)//2] self.sortedArrayToBST(nums[:len(nums)//2]) self.sortedArrayToBST(nums[len(nums)//2+1:]) return root
相关推荐
zlsdmx 2020-05-14
eroshn 2020-05-11
blncle 2020-02-11
xuanlvhaoshao 2020-01-23
wklken的笔记 2020-01-05
宿舍 2019-12-20
明月清风精进不止 2019-10-23
houdaxiami 2019-03-25
Ongoingcre 2011-09-22
jsoncorleone 2016-02-25
kekekid 2010-04-04
宁静致远 2009-06-09
timewind 2019-07-01
jsqip 2019-07-01
UsherOu 2013-02-25
静心斋 2016-03-11
ScarletLina 2011-04-09
superhosts 2019-06-26