108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

问题：一个升序的数组转变成一个高度平衡的二叉查找树（注意这里要求高度尽量平衡，就是左右子树的高度差不大于1）

思想：二叉查找树是left<=root<right这种结构的，（改题目和数组的二分查找类似）数组的中间位置的节点作为根节点，然后左半部分的中间节点作为左孩子，右半部分的中间节点作为右孩子，以此递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if(nums==null) return null; int len=nums.length; return sortedArrayToBST(nums,0,len-1); } public TreeNode sortedArrayToBST(int[] nums,int left,int right){ TreeNode root=null; if(left<=right){ int mid=left+(right-left)/2; root=new TreeNode(nums[mid]); root.left=sortedArrayToBST(nums, left, mid-1); root.right=sortedArrayToBST(nums,mid+1,right); } return root; } }