题目链接#

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

题目描述#

给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡的二叉搜索树。

这里的“高度平衡”指的是：

每个节点的左右两个子树高度差的绝对值不超过 1。

解题思路：每次取中点作为根节点#

这题最核心的一步，就是：

每次取当前有序数组的中间元素，作为这一棵子树的根节点。

为什么中点这么关键？

因为数组已经有序：

• 中点左边的元素都比它小
• 中点右边的元素都比它大

这正好满足二叉搜索树的性质：

• 左子树节点值 < 根节点值
• 右子树节点值 > 根节点值

同时，中点还能把数组尽量均匀地分成两半， 这样左右子树规模接近，整棵树就更容易保持平衡。

所以这题的套路非常清晰：

1. 取中间元素建根节点
2. 左半部分递归构造左子树
3. 右半部分递归构造右子树
4. 数组为空时返回 None

整个过程就是一个标准分治。

代码实现#

1
class Solution(object):
2
    def sortedArrayToBST(self, nums):
3
        """
4
        :type nums: List[int]
5
        :rtype: Optional[TreeNode]
6
        """
7
        def f(num_lists):
8
            if not num_lists:
9
                return None
10
            n = len(num_lists)
11
            idx = n // 2
12
            node = TreeNode(val=num_lists[idx])
13
            node.left = f(num_lists[:idx])
14
            node.right = f(num_lists[idx + 1:])
15
            return node
16

17
        if len(nums) == 0:
18
            return None
19
        return f(nums)

代码解析#

1
if not num_lists:
2
    return None

1
n = len(num_lists)
2
idx = n // 2
3
node = TreeNode(val=num_lists[idx])

1
node.left = f(num_lists[:idx])
2
node.right = f(num_lists[idx + 1:])

示例理解#

比如输入：

1
nums = [-10, -3, 0, 5, 9]

第一次取中点：

1
0

于是根节点就是：

1
0

接下来分成两段：

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

继续递归：

• 左边会选 -3 做根
• 右边会选 9 做根

然后再往下拆。

整个过程很像：

不断从中间劈开数组，再把每一块的中点拎出来当根节点。

最后就能得到一棵平衡 BST。

这份写法的优缺点#

你现在这版代码的优点很明显：

• 写法直观
• 逻辑清楚
• 很适合讲题解

但它也有一个小代价：

1
num_lists[:idx]
2
num_lists[idx + 1:]

这里每次递归都会创建新的子数组切片。

所以它虽然好懂， 但不是最省空间、最省时间的写法。

1
O(n log n)

如果想优化，可以怎么做#

更优的办法是：

• 不传子数组
• 改成传左右边界 left 和 right

这样就不会反复创建新数组， 效率会更好。

不过对于当前这题， 先把“中点分治建树”的核心讲明白更重要。 优化版可以当进阶补充， 不一定非得第一时间上。

易错点总结#

1
if not num_lists:
2
    return None

1
if len(nums) == 0:
2
    return None

1
if not num_lists:
2
    return None

1
return f(nums)

小结#

这题的核心其实就一句：

每次取有序数组的中点作为根节点，再递归构造左右子树。

这样做可以同时满足两件事：

• 保证二叉搜索树性质
• 尽量保持整棵树高度平衡

所以它本质上是一道非常典型的分治递归建树题。 数组一劈两半，中点上位称王；左边去建左树，右边去建右树，整套动作行云流水。 只要边界别漏，这题基本就是递归稳稳拿下。🦐