LeetCode 108. 将有序数组转换为二叉搜索树【Java】

这道题的题意是：给定一个已经按升序排好序的整数数组nums，要求我们把它转换成一棵平衡二叉搜索树。

一开始看到“数组”和“二叉搜索树”这两个东西放在一起，可能会有点没思路。其实这题真正想考的是：能不能想到二叉搜索树的中序遍历结果是升序的。题目现在直接给了一个升序数组，也就相当于给了我们一棵二叉搜索树中序遍历后的结果。我们要做的，就是反过来把这棵树构造出来。

不过这里还有一个限制：构造出来的二叉搜索树必须是平衡的。也就是说，不能随便构造一棵满足大小关系的树，还要尽量让它左右两边不要差太多。

题目分析

二叉搜索树有一个很重要的性质：

左子树所有节点的值 < 根节点的值 < 右子树所有节点的值

而题目给出的数组已经是升序排列的，所以如果我们从数组中选一个元素作为根节点，那么它左边的元素天然都比它小，可以放到左子树；它右边的元素天然都比它大，可以放到右子树。

比如数组：

[-10, -3, 0, 5, 9]

如果选择0作为根节点，那么：

左边：[-10, -3] 根：0 右边：[5, 9]

这样就刚好符合二叉搜索树的结构。

问题是：根节点应该选谁？

如果每次都选最左边的元素作为根节点，树可能会变成这样：

这虽然满足二叉搜索树的性质，但它明显不平衡，更像是一条链表。题目要求的是平衡二叉搜索树，所以这种做法不合适。

比较合适的做法是：每次选择当前区间的中间元素作为根节点。

这样做的好处很直接：中间元素左边和右边的元素数量差不多，递归构造出来的左右子树高度也就不会差太多，整棵树自然比较平衡。

解题思路

这道题可以用递归来做。我们不要试图一次性把整棵树想完，而是把问题拆成一个重复的小问题：

给定数组中的一段区间，用这段区间构造一棵平衡二叉搜索树。

假设当前处理的区间是[left, right]，那么我们要做的事情就是：

1. 找到这个区间的中间位置mid；
2. 用nums[mid]创建当前子树的根节点；
3. 用[left, mid - 1]这段区间递归构造左子树；
4. 用[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;

这样上一层递归就能把这个节点接到自己的左子树或右子树上。

总结

这道题的关键不是代码有多复杂，而是要想到：升序数组可以看成二叉搜索树的中序遍历结果。

既然数组已经有序，那么选一个元素作为根节点时，它左边的元素就可以放到左子树，右边的元素就可以放到右子树。为了让树保持平衡，每次都选当前区间的中间元素，这样左右两边的节点数量会比较接近。

所以本题的核心思路可以压缩成一句话：

每次取当前区间的中间元素作为根节点，再递归构造左右子树。

掌握这个思路之后，后面遇到“有序数组 / 有序链表 + 构造平衡二叉搜索树”这类题，就会更容易联想到递归和中点划分。