本文共 1071 字,大约阅读时间需要 3 分钟。
题目:
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
# Definition for a binary tree node.class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if len(nums)==0: return None if len(nums)==1: return TreeNode(nums[0]) mid = len(nums)/2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[0:mid]) root.right = self.sortedArrayToBST(nums[mid+1:len(nums)]) return root
转载地址:http://vzhci.baihongyu.com/