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

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

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

二、解题思路

✅ 题目关键点

1. 升序数组 → 所以中间的元素最适合做根节点。

2. 平衡 BST → 任意一个节点的左右子树高度差不超过 1。

---

🧠 解题思路

我们使用 递归 + 分治 的方式：

1. 找到当前数组的“中间元素”，作为根节点。

2. 左半部分递归构建左子树，右半部分递归构建右子树。

3. 返回根节点。

---

✅ 图示说明

假设数组是 [ -10, -3, 0, 5, 9 ]

• 中间是 0 → 设为根节点

• 左边 [ -10, -3 ] → 构建左子树

• 右边 [ 5, 9 ] → 构建右子树

构建完就得到一棵平衡的 BST。

三、代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return buildBST(nums, 0, nums.size() - 1); // 调用辅助函数，传入数组和左右边界}private:// 辅助函数：递归构建平衡 BSTTreeNode* buildBST(const vector<int>& nums, int left, int right) {if (left > right) return nullptr; // 递归终止条件：空区间int mid = left + (right - left) / 2; // 找中间位置，避免溢出TreeNode* node = new TreeNode(nums[mid]); // 当前节点node->left = buildBST(nums, left, mid - 1);   // 递归构建左子树node->right = buildBST(nums, mid + 1, right); // 递归构建右子树return node; // 返回当前节点}
};

四、复杂度分析

• 时间复杂度：O(n)
  每个元素都恰好被访问一次。

• 空间复杂度：O(log n)（递归栈空间）
  取决于树的高度，平衡 BST 的高度是 log 级别。