Python教程：将有序数组转换为二叉搜索树

题目：

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

成都创新互联是由多位在大型网络公司、广告设计公司的优秀设计人员和策划人员组成的一个具有丰富经验的团队，其中包括网站策划、网页美工、网站程序员、网页设计师、平面广告设计师、网络营销人员及形象策划。承接：成都做网站、网站建设、网站改版、网页设计制作、网站建设与维护、网络推广、数据库开发,以高性价比制作企业网站、行业门户平台等全方位的服务。

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

示例:

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

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

     
0
    
/ 
\
  
-3   
9
  
/   
/
-10  
5

解题思路

思路：递归

先看题目所给出的要求以及限制。

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

在这里，可以看到有序数组是按照升序排序的。我们知道，二叉搜索树（BST）中序遍历就是升序序列，那么我们可以从这个角度出发，那么问题就转变为 从中序遍历的序列中恢复二叉搜索树。

那么任选一个元素作为根节点，以元素左边的序列构建左子树，右边序列构建右子树。

但是由于有限制条件，需要转换为高度平衡二叉树，根据前面给出高度平衡二叉树的概念。那么我们考虑选择数组的中间元素作为根节点来代替前面的任意选择一个元素。

具体的实现代码如下。

代码实现

# Definition 
for a binary tree node.
# class TreeNode:
#     def __init__(
self, x):
#         
self.val = x
#         
self.left = 
None
#         
self.right = None

class Solution:
   def sortedArrayToBST(
self, nums: List[int]) -> TreeNode:
       def dfs(left, right):
           
if left > right:
               # 表示空子树
               
return 
None
           
           # 选取中间元素为根节点
           mid = left + (right-left) 
// 2

            root = TreeNode(nums[mid])
            # 中间元素左边序列构建左子树
            # 右边序列构建右子树
            root.left = dfs(left, mid-1)
            root.right = dfs(mid+1, right)

            return root
        
        return dfs(0, len(nums)-1)

实现结果

总结

• 题目中提示，有序数组是按照升序排序的，要将其转换为高度平衡的二叉搜索树。因为数组按照升序排序，而 BST 中序遍历的序列是升序序列。那么题目所求可变为求中序遍历序列转换为高度平衡二叉搜索树。

• 因为题目要求转换为高度平衡二叉搜索树，那么在数组中，应该取中间元素作为根节点。中间元素左边序列构建左子树，右边序列构建右子树。