题目描述：
题解：
public class ConvertSortedArrayToBinarySearchTree { /** * hint: 数组已经排序，用类似二分的手段将数组分开建树，最后的高度差一定小于等于一，因为左右子树最多只会相差一个元素 * @param nums * @return */ public TreeNode sortedArrayToBST2(int[] nums) { if (nums == null || nums.length < 1) { return null; } else if (nums.length==1) { return new TreeNode(nums[0]); } else { return buildTree(nums,0,nums.length-1); } } private TreeNode buildTree(int[] nums, int left, int right) { if (left == right) { return new TreeNode(nums[left]); } if (left > right) return null; int mid = left + ((right-left)>>1); TreeNode root = new TreeNode(nums[mid]); TreeNode leftTree = buildTree(nums, left, mid - 1); TreeNode rightTree = buildTree(nums, mid + 1, right); root.left = leftTree; root.right = rightTree; return root; } /** * 失败解法：边建树，边调整，最后生成平衡树，但是平衡树的调整很麻烦 * @param nums * @return */ public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length < 1) { return null; } else if (nums.length==1) { return new TreeNode(nums[0]); } else { TreeNode root = new TreeNode(nums[0]); int len = nums.length; for (int i = 1; i < len; i++) { addElement(nums[i],root); adjustTree(root); } return root; } } private void adjustTree(TreeNode root) { if (Math.abs(getHeight(root.left)-getHeight(root.right)) > 1) { // 调整二叉树 -- 不会写 } } // 获取二叉树的高度 private int getHeight(TreeNode root) { if (root == null) { return 0; } int heightOfLeft = getHeight(root.left); int heightOfRight = getHeight(root.right); return Math.max(heightOfLeft,heightOfRight) + 1; } private void addElement(int num, TreeNode root) { if (num >= root.val) { if (root.right == null) { root.right = new TreeNode(num); return; } else { addElement(num,root.right); } } else { if (root.left == null) { root.left = new TreeNode(num); return; } else { addElement(num,root.left); } } } }