将有序数组转换成二叉排序树

题目

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

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

示例

分析

这道题我想了好久，知道平衡二叉树进行中序遍历就会变成一个递增数组。反过来给你你个递增数组让你构建一个平衡二叉树就懵逼了，结果画了好久的图，看了别人的题解才做出来。 画图如下：

代码如下：

public TreeNode sortedArrayToBST(int[] nums) { if(nums.length <= 0){ return null; } return buildTree(nums, 0, nums.length - 1); } private TreeNode buildTree(int[] nums, int left, int right){ if(left > right){ return null; } int index = (left + right)/2; //数组中间值作为根节点 TreeNode root = new TreeNode(nums[index]); //递归根节点的左子树为数组0-(index-1)的数 root.left = buildTree(nums, left, index - 1); //递归右子树 root.right = buildTree(nums, index + 1, right); return root; }