题解 | #将升序数组转化为平衡二叉搜索树#

平衡二叉搜索树：树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1。

对于升序数组，就取中间值，左右节点的数目相差小于等于1。取左侧构造左子树，右侧构造右子树即可。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] nums) {
        // write code here
        // 从中间划分开数组，一半为左子树，另一半为右子树
        if (nums == null || nums.length == 0) {
            return null;
        }

        TreeNode root = createTree(nums, 0, nums.length);
        return root;
    }

    private TreeNode createTree(int[] nums, int start, int end) {
        if (start == end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = createTree(nums, start, mid);
        root.right = createTree(nums, mid + 1, end);

        return root;
    }
}