1, 题目

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

示例:

  1. 给定有序数组: [-10,-3,0,5,9],
  2. 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
  3.      0
  4.     / \
  5.   -3   9
  6.   /   /
  7. -10  5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. #scala
  2. object Solution {
  3.     def sortedArrayToBST(nums: Array[Int]): TreeNode = {
  4.         f(nums, 0, nums.length)
  5.     }
  7.     def f(nums: Array[Int], start: Int, end: Int): TreeNode = {
  8.         if (start < end) {
  9.             val root = new TreeNode(nums(start + (end - start) / 2))
  10.             root.left = f(nums, start, start + (end - start) / 2 )
  11.             root.right = f(nums, start + (end - start) / 2 + 1, end)
  12.             root
  13.         } else {
  14.             null
  15.         }
  16.     }
  17. }
  1. #python
  2. class Solution:
  3.     def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
  4.         return self.f(nums, 0, len(nums))
  6.     def f(self, nums: List[int], start: int, end: int):
  7.         if start < end:
  8.             middle = start + (end - start) // 2
  9.             root = TreeNode(nums[middle])
  10.             root.left = self.f(nums, start, middle)
  11.             root.right = self.f(nums, middle + 1, end)
  12.             return root
  13.         else:
  14.             return None