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

题目

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

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

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

     0
    / \
  -3   9
  /   /
-10  5

方法

由于二叉搜索树的中序遍历是升序的，因此本题相当于根据中序遍历的序列恢复二叉搜索树。因此我们可以拿序列中的任何一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样就可以得到一颗二叉搜索树。又因为题目要求得到一颗平衡搜索二叉树BST，因此我们选择升序序列中的中间元素作为根节点。

代码

class Solution {
    private int[] nums;
    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0, nums.length - 1);
    }
    //dfs函数用数组nums中从索引left到right间的元素构造二叉搜索树，返回构造后树的根节点。
    public TreeNode dfs(int left, int right){
        if(left > right)
            return null;
        int mid = left + ((right - left) >> 1)
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(left, mid - 1);
        root.right = dfs(mid + 1, right);
        return root;
    }
}

本题的拓展为109.有序链表转换二叉搜索树.两道题思路完全一样，只不过链表无法像数组一样通过索引直接找到中间元素，需要用快慢指针法找中间元素。