这是悦乐书的第166次更新，第168篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第25题（顺位题号是108）。给定一个数组，其中元素按升序排序，将其转换为高度平衡的二叉搜索树。例如：
给定排序数组：[ -10，-3, 0, 5, 9]
一个可能的答案是：[0，-3, 9，-10，null，5]，它代表以下高度平衡的二叉搜索树：
0
/ \
-3 9
/ /
-10 5
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 相关概念
在探讨如何解题前，我们先把题目中的两个概念弄清楚。
二叉搜索树，是一棵空树，或者是具有下列性质的二叉树：
1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）任意节点的左、右子树也分别为二叉搜索树
总结一下就是任意节点的值始终满足 左节点值 < 根节点值 < 右节点值 这个条件。
平衡二叉树，是一颗空树，或者具有下列性质的二叉树：
1）左子树是一颗二叉平衡树
2）右子树是一颗二叉平衡树
3）左右两个子树的高度差的绝对值不超过1
总结一下就是 |左子树层数-右子树层数| <= 1 。
另外，我们再来了解下二叉树中序遍历这个概念，这对我们解题会有所帮助。
中序遍历，如果二叉树不为空，则会首先遍历左子树，然后访问根节点，最后遍历右子树。
A
/ \
B C
/ \ /
D E F
上面的二叉树中序遍历的结果是：DBEAFC 。
03 解题
我们发现那个给出的示例数组，其实就是那个二叉平衡搜索树的中序遍历结果，数组的中间值就是二叉树的根节点，往前就是左子树，往后就是右子树，所以我们可以借助二分法，将数组分为三部分，第一部分从首位到中间位，第二部分是中间位，第三部分是中间位到尾位，利用这三部分分别递归给二叉树设值即可。
public TreeNode sortedArrayToBST(int[] nums) {
return addNode(nums, 0, nums.length-1);
}
public TreeNode addNode(int[] nums, int left, int right){
if (left > right) {
return null;
}
int mid = (right + left)/2;
TreeNode t = new TreeNode(nums[mid]);
t.left = addNode(nums, left, mid-1);
t.right = addNode(nums, mid+1, right);
return t;
}
04 小结
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！