1、题目

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 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] 都是高度平衡二叉搜索树。

2、链接

题目：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

视频：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树_哔哩哔哩_bilibili

3、解题思路

那我就瞎写了，希望复习回来的时候自己还记得

典型的双指针法+递归

注意题目给的是平衡二叉树，所以我们只要把这个有序数组nums取中间值作为二叉树的根节点就好了

还要注意的事，使用双指针一定要规定好左右区间，本文我用的是左闭右开--> [left, right)

递归三部曲：

1.确定函数返回值和传入参数

TreeNode* traversal(vector<int>& nums, int left, int right)

2.确定终止条件

这个递归到什么时候结束呢，显而易见是在区间不断缩减的过程中，出现了区间不成立的时候

if (left >= right) return nullptr;

md直到现在我才想通为什么递归最后一层返回的事nullptr，因为最下一层叶子指向的是nullptr啊，return这个关键词告诉程序递归结束，顺便抛出了一个nullptr放在最后一层的下面罢了

3.确定单层递归逻辑

前面说了，找nums这个有序数组的中值作为二叉树的根节点，怎么找呢？

用int mid = (left + right) / 2;？那可不行，万一right == INT_MAX不就越界了吗。所以应该这样写：int mid = left + ((right - left) / 2);

千万别觉着mid是小数怎么办，小数会被自动向下取整变为整数，莫得影响

        int mid = left + (right - left) / 2; //自动转换小数，向下取整TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid);root->right = traversal(nums, mid+1, right);return root;

展示一下随手画的东西：（这什么破编辑界面都不能旋转图片）

递归完就是这个东西：

4、全部代码

最近懒得让AI给我注释代码了，因为的确简单的很，没必要

class Solution {
public://nums取地址的原因是：不取地址每次递归都会重新复制内存，空间消耗大TreeNode* traversal (vector<int>& nums, int left, int right) {if (left >= right) return nullptr; // [ )//int mid = (left + right) / 2; //如果right是int最大值，就会越界int mid = left + (right - left) / 2; //自动转换小数，向下取整TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid);root->right = traversal(nums, mid+1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = traversal(nums, 0, nums.size());return root;}
};