【LeetCode刷题日记】108.将有序数组转换为二叉搜索树
🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！
前言：
大家好，我是代码不加冰，又到了我们每日的刷题环节，今天刷的题目是关于二叉搜索树的，让我们一起来看看吧。
题目背景：108.将有序数组转换成二叉搜索树
给你一个整数数组
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 <= 104-104 <= nums[i] <= 104nums按严格递增顺序排列
题目解析：
解题思路
核心思想：因为数组是有序的，BST 的中序遍历就是升序序列。要构建高度平衡的 BST，每次选择数组中间的元素作为根节点，这样左右子树的元素个数相差不超过 1。
递归步骤：
如果数组区间无效（
left > right），返回null找到中间位置
mid = left + (right - left) / 2创建根节点
new TreeNode(nums[mid])递归构建左子树：
root.left = build(left, mid - 1)递归构建右子树：
root.right = build(mid + 1, right)返回根节点
递归三部曲：
确定递归函数返回值及其参数
删除二叉树节点，增加二叉树节点，都是用递归函数的返回值来完成，这样是比较方便的。
相信大家如果仔细看了前面的文章，一定会对递归函数返回值的作用深有感触。
那么本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。
再来看参数，首先是传入数组，然后就是左下标left和右下标right，我们在前面中提过，在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组。
所以代码如下：
// 左闭右闭区间[left, right] TreeNode* traversal(vector<int>& nums, int left, int right)这里注意，我这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量。
确定递归终止条件
这里定义的是左闭右闭的区间，所以当区间 left > right的时候，就是空节点了。
代码如下：
if (left > right) return nullptr;
- 确定单层递归的逻辑
首先取数组中间元素的位置，不难写出
int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法中尤其需要注意所以可以这么写：
int mid = left + ((right - left) / 2);直觉写法（有bug）
大多数人第一反应是：
java int mid = (left + right) / 2;问题：当
left和right都很大时（比如接近Integer.MAX_VALUE），left + right可能会溢出，变成负数，导致mid计算错误。方法2：安全写法（防溢出）
java int mid = left + (right - left) / 2;推导过程：
text 目标：求 left 和 right 的中点 (left + right) / 2 = left/2 + right/2 = left + (right - left)/2 ← 变形验证：假设
left = 4,right = 10text 方式1：(4 + 10) / 2 = 14 / 2 = 7 方式2：4 + (10 - 4) / 2 = 4 + 6/2 = 4 + 3 = 7防溢出原理：
right - left最大值 ≈ 数组长度 ≤ 10^4，不会溢出
left + 一个小数也不会溢出最后返回root节点，单层递归整体代码如下：
int mid = left + ((right - left) / 2); TreeNode* root = new TreeNode(nums[mid]); root->left = traversal(nums, left, mid - 1); root->right = traversal(nums, mid + 1, right); return root;这里
int mid = left + ((right - left) / 2);的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的。
图解示例
输入：nums = [-10, -3, 0, 5, 9]
构建过程
text 第1步：left=0, right=4, mid=2, root=0 0 / \ 左子树 右子树 [-10,-3] [5,9] 第2步：左子树 left=0, right=1, mid=0, root=-10 0 / \ -10 右子树 \ -3 第2步：右子树 left=3, right=4, mid=3, root=5 0 / \ -10 5 \ \ -3 9最终结果（一种可能的平衡 BST）：
text
0 / \ -10 5 \ \ -3 9
为什么这样构建是平衡的
| 性质 | 说明 |
|---|---|
| 中间元素作根 | 左右子树元素个数差 ≤ 1 |
| 递归构建 | 每个子树也都是平衡的 |
| BST 性质 | 左子树所有值 < 根 < 右子树所有值（因为数组升序） |
复杂度分析
时间复杂度：O(n)，每个节点只访问一次
空间复杂度：O(log n)，递归栈深度（平衡二叉树的高度）
多种中间点选择方式
代码中int mid = left + (right - left) / 2选择的是左中位数。你也可以选择右中位数：
java // 右中位数（数组长度为偶数时选靠右的） int mid = left + (right - left + 1) / 2;不同的选择会产生不同形状的 BST，但都是平衡的。例如[-10,-3,0,5,9]：
| 中间点选择 | 根节点 |
|---|---|
| 左中位数 (index 2) | 0 |
| 右中位数 (index 3) | 5 |
题目答案：
递归法：
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 = left + (right - left) / 2; TreeNode root = new TreeNode(nums[mid]); // 递归构建左右子树 root.left = build(nums, left, mid - 1); root.right = build(nums, mid + 1, right); return root; } }迭代法：
class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length == 0) return null; //根节点初始化 TreeNode root = new TreeNode(-1); Queue<TreeNode> nodeQueue = new LinkedList<>(); Queue<Integer> leftQueue = new LinkedList<>(); Queue<Integer> rightQueue = new LinkedList<>(); // 根节点入队列 nodeQueue.offer(root); // 0为左区间下标初始位置 leftQueue.offer(0); // nums.size() - 1为右区间下标初始位置 rightQueue.offer(nums.length - 1); while (!nodeQueue.isEmpty()) { TreeNode currNode = nodeQueue.poll(); int left = leftQueue.poll(); int right = rightQueue.poll(); int mid = left + ((right - left) >> 1); // 将mid对应的元素给中间节点 currNode.val = nums[mid]; // 处理左区间 if (left <= mid - 1) { currNode.left = new TreeNode(-1); nodeQueue.offer(currNode.left); leftQueue.offer(left); rightQueue.offer(mid - 1); } // 处理右区间 if (right >= mid + 1) { currNode.right = new TreeNode(-1); nodeQueue.offer(currNode.right); leftQueue.offer(mid + 1); rightQueue.offer(right); } } return root; } }