108、将有序数组转换为高度平衡二叉搜索树

此题首先可以确定选用的算法是递归

对于二叉搜索树我们可以知道其左叶子节点值<根节点值<右叶子节点值，故二叉搜索树的中序遍历为一个升序数组。即题目给的有序数组。

中序遍历：先遍历左子树，在遍历根节点，最后遍历右子树。 如果不要求为平衡二叉搜索树的话，仅由一个升序数组，树的根节点就有多种不同的取值，就会产生很多个不同的二叉搜索树。

如当升序数组为：[-10,-3,0,5,9]时，几种可能的情况为(还有其他情况，可以自己看一下，比较特殊)： 如果要求为平衡二叉搜索树的话，即左右子树的最大高度差要小于等于1，所以选中的根节点左右子树的节点数量差要小于等于1，即选中升序数组的一个值其左边元素数的右边元素数的差要小于等于1。

这样就可以先求出升序数组的中间值即根节点然后左边的就为左子树，右边的为右子树，然后对左右子树再次执行相同的操作，一直递归知道最后更节点的左右子树均为空即可。

由于数组长度可能为偶数也可能为奇数，所以选择的中间值可能有差别，故最后产生的树就会不一样，这里我们采用当数组长度为奇数时，中间值即为所求，数组长度为偶数时，有两个中间值我们选取左边的为根节点（当然也可以选择右边的）。 则求得中间值的公式为：  mid = (left+right)/2  mid = (left+right)>>1  mid = left+(rgiht-left)/2 以上三个公式均可，建议使用方式2，方式1当数组长度较大时肯能产生溢出带来不必要的麻烦，不过一般不会发生。

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } @Override public String toString() { return "TreeNode{" + "val=" + val + ", left=" + left + ", right=" + right + '}'; } } public class Test108 { public static void main(String[] args) { int[] nums = {-10,-3,0,5,9}; Test108 test108 = new Test108(); test108.sortedArrayToBST(nums); } //中序遍历，总是选择中间位置左边的数字作为根节点 //选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2，此处的除法为整数除法。 //但是这样计算有溢出风险，使用mid = left+(right-left)/2或者移位运算较合适 public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); } public TreeNode helper(int[] nums, int left, int right) { if (left > right) { return null; } // 总是选择中间位置左边的数字作为根节点 int mid = (left + right) / 2; System.out.println(left+"--"+right+"--"+mid); TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums, left, mid - 1); root.right = helper(nums, mid + 1, right); System.out.println(root); return root; }

结果为：

TreeNode{val=0, left=TreeNode{val=-10, left=null, right=TreeNode{val=-3, left=null, right=null}}, right=TreeNode{val=5, left=null, right=TreeNode{val=9, left=null, right=null}}}

图示：

选择其它位置为根节点类似，可自行推导。