题目描述

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

我的解法——DFS（AC）

递归进行。每次找到排序数组的中点，中点左边的子排序数组构成左子树，中点右边的子排序数组构成右子树。就这样递归进行。由于每次都几乎做到了二分，所以每次的左子树和右子树的节点数量是均衡的，所以最后得到的BST树是balanced。(我不知道如何严格地证明它。)
注意递归边界
传递nums是值传递，不是引用传递，所以每次递归调用SortedArrayToBST函数时，它会再次复制这个大vector。所以在递归过程中,这种行为将花费很大内存。
时间时间复杂度均为O(n)，空间复杂度为O(1)。
Beat88%

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

class Solution(object):
    def mysortedArrayToBST(self, nums, l, r):
        m = (r - l) / 2 + l
        now = TreeNode(nums[m])
        if(m - 1 >= l):
            now.left = self.mysortedArrayToBST(nums, l, m - 1)
        if(m + 1 <= r):
            now.right = self.mysortedArrayToBST(nums, m + 1, r)
        return now
    
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if(len(nums) == 0):
            return None
        return self.mysortedArrayToBST(nums, 0, len(nums) - 1)