Python教程：将有序数组转换为二叉搜索树-创新互联

题目：

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

创新互联建站主营博罗网站建设的网络公司,主营网站建设方案,app软件开发公司,博罗h5微信小程序定制开发搭建,博罗网站营销推广欢迎博罗等地区企业咨询

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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)

实现结果

本文名称：Python教程：将有序数组转换为二叉搜索树-创新互联
链接URL：http://mswzjz.cn/article/phehs.html