2020.07.03 周五 题目：108将有序数组转换为二叉搜索树 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例: 给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0 / \ -3 9 / / -10 5——————————我是分割线—————————— 解法： 思路：二叉搜索树的中序遍历是升序序列，故给定的数组是中序遍历序列，但是给定二叉树的中序遍历不能唯一确定二叉树。举几个例子，可能的树：
5 | 0 | 5 / \ | / \ | / \ 0 9 | -3 5 | -3 9 / | / \ | / \ -3 | -10 9 |-10 0 / | -10 |现增加一个限制条件——高度平衡，但是也不能唯一确定二叉树。举几个例子，可能的树：
0 | 0 | 0 / \ | / \ | / \ -10 9 | -3 5 | -3 9 \ / | / \ | / \ -3 5 | -10 9 | -10 5故选中间数字作为根节点，这样分给左右子树的数字个数相同（总数为奇数个）或者差一个（总数为偶数个）。 如果数组长度是奇数，则选中间数字作为根节点，根节点唯一；如果数组长度是偶数，则选中间位置左/右边的数作为根节点（下面我将选左边的数）。 确定根节点后，根节点左边的数字为左子树，右边为右子树。且左右子树均为平衡二叉树->递归 递归的基准是二叉树为空。
代码：
# leetcode108将有序数组转换为二叉搜索树 2020.07.03 # 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): # 以[-10,-3,0,5,9]为例 """ :type nums: List[int] :rtype: TreeNode """ if not nums: #如果nums空则平衡二叉搜索树为空 return None #以中间位置左边的数字作为根节点 如len为5 则mid=5//2=2 即下标为2的元素0为根节点 mid = len(nums)//2 root = TreeNode(nums[mid]) #左子树有下标为0到下标为mid2的元素（左闭右开） 即-10和-3 root.left = self.sortedArrayToBST(nums[:mid]) #右子树有下标为mid+1=3到末尾的元素 即5和9 root.right = self.sortedArrayToBST(nums[mid+1:]) return root