What is the key idea in Convert Sorted Array to Binary Search Tree?

Choose the middle element of each sorted segment as the root of that segment. That single rule preserves BST ordering and keeps left and right subtree sizes close enough to maintain height balance.

Why does the midpoint guarantee a height-balanced BST?

Because the midpoint splits the sorted array into two nearly equal halves. Each recursive call repeats the same balanced split, so subtree heights differ by at most about one level instead of drifting into a long chain.

Can I use either middle element when the segment length is even?

Yes. For an even-length range, either the left middle or right middle creates a valid height-balanced BST. The output tree shape may differ, but both still satisfy the problem because the answer is not unique.

Why is passing indices better than slicing arrays here?

Index bounds keep the recursion focused on the original array without allocating new lists. That avoids extra copying, keeps the implementation closer to O(log n) auxiliary space, and reduces off-by-one mistakes once ranges get small.

Is binary-tree traversal and state tracking the real pattern for this problem?

The stronger core pattern is divide and conquer on sorted ranges, with state tracking limited to the current left and right bounds. Traversal matters less than choosing the correct midpoint and preserving exact child ranges at each step.

#108

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。示例 1：输入： nums = [-10,-3,0,5,9] 输出： [0,-3,9,-10,null,5] 解释： [0,-10,5,null,-3,null,9] 也将被视为正确答案：示例 2：…

数组分治树二叉搜索树二叉树

题目描述

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

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 按 严格递增 顺序排列

lightbulb

解题思路

方法一：二分 + 递归

我们设计一个递归函数 $\textit{dfs}(l, r)$ ，表示当前待构造的二叉搜索树的节点值都在数组 $\textit{nums}$ 的下标范围 $[l, r]$ 内。该函数返回构造出的二叉搜索树的根节点。

函数 $\textit{dfs}(l, r)$ 的执行流程如下：

如果 $l > r$ ，说明当前数组为空，返回 null。
如果 $l \leq r$ ，取数组中下标为 $\textit{mid} = \lfloor \frac{l + r}{2} \rfloor$ 的元素作为当前二叉搜索树的根节点，其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。
递归地构造当前二叉搜索树的左子树，其根节点的值为数组中下标为 $\textit{mid} - 1$ 的元素，左子树的节点值都在数组的下标范围 $[l, \textit{mid} - 1]$ 内。
递归地构造当前二叉搜索树的右子树，其根节点的值为数组中下标为 $\textit{mid} + 1$ 的元素，右子树的节点值都在数组的下标范围 $[\textit{mid} + 1, r]$ 内。
返回当前二叉搜索树的根节点。

答案即为函数 $\textit{dfs}(0, n - 1)$ 的返回值。

时间复杂度 $O(n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(l: int, r: int) -> Optional[TreeNode]:
            if l > r:
                return None
            mid = (l + r) >> 1
            return TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r))

        return dfs(0, len(nums) - 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you see that choosing the middle element is what satisfies both BST ordering and height balance at the same time?
question_mark
Can you explain why using left and right indices is safer here than repeatedly slicing the array into subarrays?
question_mark
Will you handle even-length ranges consistently and show that either middle choice still produces a valid height-balanced BST?

warning

常见陷阱

外企场景

error
Using the first or last element as each root, which preserves BST order but creates a skewed tree instead of a height-balanced one.
error
Recursing on the wrong ranges, such as including mid in a child call again, which causes infinite recursion or duplicate nodes.
error
Building with array slices everywhere, which still works logically but quietly increases memory use and can hurt performance on large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Convert a sorted singly linked list to a height-balanced BST, where random access is gone and midpoint handling changes.
arrow_right_alt
Build the BST iteratively from a sorted array using an explicit queue or stack of index ranges instead of recursion.
arrow_right_alt
Given a sorted array, return any height-balanced BST but prefer the left middle or right middle consistently for even-length segments.

help

常见问题

外企场景

继续练习

#109 有序链表转换二叉搜索树 #106 从中序与后序遍历序列构造二叉树 #105 从前序与中序遍历序列构造二叉树