取中点为根，递归构造左右半段，天然平衡。
OJ: leetcodecn
题目 ID: convert-sorted-array-to-binary-search-tree
难度:入门
标签:BST递归分治cpppython
日期: 2026-07-29 13:10
题意
将升序数组转换为高度平衡的 BST。
思路
每次取中间元素为根，递归构造左右子树。中序遍历结果即为原数组。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &nums) {
function<TreeNode *(int, int)> build = [&](int l, int r) -> TreeNode * {
if (l > r)
return nullptr;
int m = (l + r) / 2;
TreeNode *root = new TreeNode(nums[m]);
root->left = build(l, m - 1);
root->right = build(m + 1, r);
return root;
};
return build(0, nums.size() - 1);
}
};
vector<int> inorder;
void dfs(TreeNode *r) {
if (!r)
return;
dfs(r->left);
inorder.push_back(r->val);
dfs(r->right);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int &x : a)
cin >> x;
auto r = Solution().sortedArrayToBST(a);
dfs(r);
for (int x : inorder)
cout << x << ' ';
return 0;
}python
#!/usr/bin/env python3
from typing import List, Optional
class TreeNode:
def __init__(self, x):
self.val = x
self.left = self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(l, r):
if l > r:
return None
m = (l + r) // 2
root = TreeNode(nums[m])
root.left = build(l, m - 1)
root.right = build(m + 1, r)
return root
return build(0, len(nums) - 1)
def inorder(r):
if not r:
return []
return inorder(r.left) + [r.val] + inorder(r.right)
def main():
n = int(input())
a = list(map(int, input().split()))
print(*inorder(Solution().sortedArrayToBST(a)))
if __name__ == "__main__":
main()复杂度
时间 O(n)，空间 O(log n) 递归栈。
总结
有序数组转 BST 的本质是二分递归。