|
题目来源：https://leetcode-cn.com/problems/minimum-height-tree-lcci/
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,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 nums:
mid = len(nums) / 2 # 找中位数
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid]) # 找左子中位数
root.right = self.sortedArrayToBST(nums[mid + 1:]) # 找右子中位数
return root
| 
转播
