（力扣每日一题）将有序数组转换为二叉搜索树

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

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

0 / \

-3 9 / / -10 5 解题思路 1、由题意得知数组是按照升序排列的有序数列，所以可以确保数组是二叉搜索树的中序遍历序列。（二叉搜索树的中序遍历是升序序列） 2、确定二叉搜索树（不唯一）的根节点： （1）选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡。 （2）如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点。 （3）用递归的方式创建平衡二叉搜索树。

方法一：中序遍历，选择中间位置左边的数字作为根节点 根节点的下标为 mid=(left+right)/2 代码

class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: #定义左节点和右节点 def helper(left, right):#helper用来实现辅助功能 if left > right: return None # 总是选择中间位置左边的数字作为根节点 mid = (left + right) // 2 #利用递归建立二叉搜索树 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1)

方法二：中序遍历，总是选择中间位置右边的数字作为根节点 选择中间位置右边的数字作为根节点，则根节点的下标为mid=(left+right+1)/2

class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: #定义左节点和右节点 def helper(left, right): if left > right: return None # 总是选择中间位置右边的数字作为根节点 mid = (left + right + 1) // 2 #利用递归建立二叉搜索树 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1)

方法三：中序遍历，选择任意一个中间位置数字作为根节点 选择任意一个中间位置数字作为根节点，则根节点的下标为 mid=(left+right)/2和 mid=(left+right+1)/2两者中随机选择一个 代码

class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def helper(left, right): if left > right: return None # 选择任意一个中间位置数字作为根节点 mid = (left + right + randint(0, 1)) // 2 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1)

三个方法的复杂度都是 时间复杂度：O(n) 空间复杂度：O(log n)

总结 三个方法主要的区别在于根节点mid的选取不同，总的来说二叉搜索树的构成就是由一级一级不断选取根节点来完成的。