108.md

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

思路

• 二叉搜索树：就是二叉查找树，左节点小于根节点，右节点大于根节点
• 高度平衡：空（null）叶子节点高度差小于等于 1
• [-10,-3,0,5,9] 有下面这几种答案：

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

      0                 0               0               0
     / \               / \             / \             / \
   -3   9           -10   9          -3   5         -10   5
   /   /              \  /           /     \          \    \
 -10  5              -3 5          -10      9         -3    9

• 技巧：选择中位数作为根节点，再在左右两边选择一个中位数作为左右子树的根节点
• 时间复杂度：O(n)，n 为数组的长度，需要遍历每个节点
• 标签：中位数

代码

# Python3
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if nums == []:
            return
        middleIndex = int(len(nums)/2)
        root = TreeNode(nums[middleIndex])
        root.left = self.sortedArrayToBST(nums[0:middleIndex])
        root.right = self.sortedArrayToBST(nums[middleIndex+1:len(nums)])
        return root

// Java
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        int middleIndex = (int)(nums.length/2);
        TreeNode root = new TreeNode(nums[middleIndex]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, middleIndex));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, middleIndex+1, nums.length));
        return root;
    }
}