题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

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 = None

class Solution(object):
	def sortedArrayToBST(self, nums):
		"""
		:type nums: List[int]
		:rtype: TreeNode
		"""
		if(not nums or len(nums)==0):
			return None
		def recursion(arr):
			if(not arr or len(arr)==0):
				return None
			index = len(arr)/2
			root = TreeNode(arr[index])
			arr_left = arr[:index]
			arr_right = arr[index+1:]
			root.left = recursion(arr_left)
			root.right = recursion(arr_right)
			return root
		return recursion(nums)
                                                                  

3 次阅读