python数据结构（将有序数组转换为二叉搜索树）

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

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

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

示例:

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

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

思路
关键点：构造树时，二分法选择中间节点作为根节点，产生的树是平衡二叉树

python3实现

树节点的定义

class TreeNode: def __init__(self, x): self.val = x
        self.left = None self.right = None 

１．直接传入数组的一半当做子树进行递归

from typing import List
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        n = len(nums)
        if n == 0:
            return None
        mid = n//2
        root = TreeNode( nums[mid] )
        root.left = self.sortedArrayToBST( nums[:mid] )
        root.right = self.sortedArrayToBST( nums[mid+1:])
        return root 

２传入区间索引进行递归

from typing import List
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def midDivide(l,r):
            if l > r:
                return 
            mid  = l + ( (r-l)>>1 )
            root = TreeNode( nums[mid] )
            root.left = midDivide(l, mid - 1)
            root.right = midDivide(mid + 1, r)
            return root
            
        return midDivide(0,len(nums)-1) 

本文地址：https://blog.csdn.net/qq_28757173/article/details/107100410