这道题的题意是给定一个已经按升序排好序的整数数组nums要求我们把它转换成一棵平衡二叉搜索树。一开始看到“数组”和“二叉搜索树”这两个东西放在一起可能会有点没思路。其实这题真正想考的是能不能想到二叉搜索树的中序遍历结果是升序的。题目现在直接给了一个升序数组也就相当于给了我们一棵二叉搜索树中序遍历后的结果。我们要做的就是反过来把这棵树构造出来。不过这里还有一个限制构造出来的二叉搜索树必须是平衡的。也就是说不能随便构造一棵满足大小关系的树还要尽量让它左右两边不要差太多。题目分析二叉搜索树有一个很重要的性质左子树所有节点的值 根节点的值 右子树所有节点的值而题目给出的数组已经是升序排列的所以如果我们从数组中选一个元素作为根节点那么它左边的元素天然都比它小可以放到左子树它右边的元素天然都比它大可以放到右子树。比如数组[-10, -3, 0, 5, 9]如果选择0作为根节点那么左边[-10, -3] 根0 右边[5, 9]这样就刚好符合二叉搜索树的结构。问题是根节点应该选谁如果每次都选最左边的元素作为根节点树可能会变成这样这虽然满足二叉搜索树的性质但它明显不平衡更像是一条链表。题目要求的是平衡二叉搜索树所以这种做法不合适。比较合适的做法是每次选择当前区间的中间元素作为根节点。这样做的好处很直接中间元素左边和右边的元素数量差不多递归构造出来的左右子树高度也就不会差太多整棵树自然比较平衡。解题思路这道题可以用递归来做。我们不要试图一次性把整棵树想完而是把问题拆成一个重复的小问题给定数组中的一段区间用这段区间构造一棵平衡二叉搜索树。假设当前处理的区间是[left, right]那么我们要做的事情就是找到这个区间的中间位置mid用nums[mid]创建当前子树的根节点用[left, mid - 1]这段区间递归构造左子树用[mid 1, right]这段区间递归构造右子树。当left right的时候说明当前区间已经没有元素了这时候直接返回null递归也就停止了。整个过程其实有点像把一个有序数组不断从中间切开中间的数拿出来当根左边继续切右边继续切直到每一段都处理完。举个例子还是看这个数组[-10, -3, 0, 5, 9]第一次处理整个区间[0, 4]中间下标是2对应的值是0所以0成为根节点。0接下来处理左半部分[0, 1]也就是[-10, -3]。按照代码里的中点写法mid 0所以-10成为左子树的根节点-3会被放到它的右边。再处理右半部分[3, 4]也就是[5, 9]。中点是3所以5成为右子树的根节点9会被放到它的右边。最后得到的树大概是这样这棵树满足二叉搜索树的性质并且左右高度差也符合平衡要求。需要注意的是这道题的答案并不唯一。如果你取中点时偏右也可能构造出另一棵树只要满足平衡二叉搜索树都是可以通过的。Java 代码class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { if (left right) { return null; } int mid (right - left) / 2 left; TreeNode root new TreeNode(nums[mid]); root.left build(nums, left, mid - 1); root.right build(nums, mid 1, right); return root; } }代码说明sortedArrayToBST是递归的入口return build(nums, 0, nums.length - 1);因为一开始要用整个数组来构造二叉搜索树所以左边界是0右边界是nums.length - 1。真正的构造逻辑在build方法里private TreeNode build(int[] nums, int left, int right)这里的left和right表示当前要处理的数组范围。每一次递归都只负责当前这一小段区间不需要关心整棵树已经长成什么样。递归结束条件是if (left right) { return null; }当左边界已经超过右边界说明当前区间为空没有节点可以创建所以返回null。这个返回值会接到上一层节点的left或right上。中点的计算方式是int mid (right - left) / 2 left;这其实就是取(left right) / 2只是写法更稳一些可以避免下标相加时出现整数溢出。平时写二分、递归划分区间时都可以优先用这种写法。创建根节点TreeNode root new TreeNode(nums[mid]);当前区间的中间元素就是当前子树的根节点。然后递归构造左右子树root.left build(nums, left, mid - 1); root.right build(nums, mid 1, right);因为数组是升序的所以mid左边的元素一定都小于nums[mid]它们应该放在左子树mid右边的元素一定都大于nums[mid]它们应该放在右子树。最后返回当前根节点return root;这样上一层递归就能把这个节点接到自己的左子树或右子树上。总结这道题的关键不是代码有多复杂而是要想到升序数组可以看成二叉搜索树的中序遍历结果。既然数组已经有序那么选一个元素作为根节点时它左边的元素就可以放到左子树右边的元素就可以放到右子树。为了让树保持平衡每次都选当前区间的中间元素这样左右两边的节点数量会比较接近。所以本题的核心思路可以压缩成一句话每次取当前区间的中间元素作为根节点再递归构造左右子树。掌握这个思路之后后面遇到“有序数组 / 有序链表 构造平衡二叉搜索树”这类题就会更容易联想到递归和中点划分。