目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

二、解题思路

尽量保证对称构建二叉搜索树，可以双指针得到mid值，然后建树，类似二分查找，注意右>根>左。

三、代码

  

   

    

     

    
    

     

      # 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) -> TreeNode:
     
    
   

    

     

    
    

     

       n = len(nums)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def dfs(l, r):
     
    
   

    

     

    
    

     
 if l == r:
     
    
   

    

     

    
    

     
 return None
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       mid = (l + r) // 2
     
    
   

    

     

    
    

     

       node = TreeNode(nums[mid])
     
    
   

    

     

    
    

     

       node.right = dfs(mid + 1, r)
     
    
   

    

     

    
    

     

       node.left = dfs(l, mid)
     
    
   

    

     

    
    

     
 return node
     
    
   

    

     

    
    

     
 return dfs(0, n)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums = [-10,-3,0,5,9]
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.sortedArrayToBST(nums)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108707149