108。ConvertanorderedarraytoabinarysearchtreeTopic将一个有序数组按升序转换为高度平衡的二叉搜索树Tree。本题中，高度平衡的二叉树是指一棵二叉树的每个节点的左右子树的高度差的绝对值不超过1。例：给定一个有序数组：[-10,-3,0,5,9]，一个可能的答案是：[0,-3,9,-10,null,5]，可以表示如下高度的平衡二叉搜索树：0/\-39//-105解题思路：递归看题中给出的要求和限制条件。将按升序排列的有序数组转换为高度平衡的二叉搜索树。高度平衡二叉树：指的是每个节点的左右子树高度差的绝对值不超过1的二叉树。这里可以看到排序后的数组是按升序排序的。我们知道二叉搜索树（BST）的中序遍历是一个升序列，那么我们可以从这个角度出发，那么问题就变成了从中序遍历序列中恢复二叉搜索树。然后选择一个元素作为根节点，用该元素左边的序列构造左子树，用右边的序列构造右子树。但是由于条件限制，需要按照前面给出的高度平衡二叉树的概念，转化为高度平衡二叉树。那么我们考虑选择数组中间的元素作为根节点，来代替之前任意选择一个元素。具体实现代码如下。代码实现#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defsortedArrayToBST(self,nums:List[int])->TreeNode:defdfs(left,right):ifleft>right:#表示空子树returnNone#选择中间的元素作为根节点mid=left+(right-left)//2根=TreeNode(nums[mid])#中间元素左序列构建左子树#右序列构建右子树root.left=dfs(left,mid-1)root.right=dfs(mid+1,right)returnrootreturndfs(0,len(nums)-1)实现结果总结如题所述，有序数组按升序排序，需要转化为高度平衡的二叉查找树。因为数组是升序排列的，按BST顺序遍历的序列是升序。那么题目求的就可以转化为一个中序遍历序列，变成一个高度平衡的二叉搜索树。因为题目要求转换成高度平衡的二叉搜索树，那么在数组中，应该取中间的元素作为根节点。中间元素的左序列构建左子树，右序列构建右子树。文章原创，如果觉得写的不错，请点个关注点个赞。微信公众号《书所集录》，同步更新，欢迎关注。
