来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
8月15日阿里巴巴发布了第一财季业绩，营收2432.36亿，同比增长4%，净利润240.22亿，同比减少27%，经营活动产生的现金流量净额为336.36亿，同比下降26%。财报还公布了员工数量变化，2024年上半年员工减少2.1万，创下历史记录。各大机构很看好阿里未来的赚钱能力，纷纷上调阿里目标价，财报一经公布阿里股价大涨。
有人认为上半年有不少校招生入职，所以为社会输送的人才是多于2.1万的。大家怎样看待这份财报？
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
言归正传，今天我们来分享一道阿里面试原题「将有序数组转换为二叉搜索树」。
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡二叉搜索树。
举个例子：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
思路解析
因为题目中的数组是升序排列的，对于一棵二叉搜索树，只有对其中序遍历的时候得到的序列是升序的，所以这个数组是对二叉搜索树中序遍历的结果，而且题目中的这棵二叉搜索树是一棵平衡二叉搜索树，也就是左子树和右子树的高度相差不会超过1。如果要根据升序数组恢复这棵平衡二叉树，我们可以选择数组最中间的元素作为二叉树的根节点，递归的用最中间元素左边的子数组left生成二叉树的左子树，用最中间元素右边的子数组right生成二叉树的右子树。递归的边界条件是当子数组为空的时候，返回空节点。
如果原数组中元素个数为n，如果n为奇数，子数组left和right的大小均为(n-1)/2，这个时候左右子树的高度均为log((n - 1)/2)，如果n为偶数子数组left和right的大小分别为(n-1)/2+1和(n-1)/2， 这个时候左右子树的高度分别为log(n + 1)/2)和log(n - 1)/2)，两种情况都可以保证左右子树的高度相差不超过1。
下面我们给出c++和python的两种代码实现。
c++代码
/**
* 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 help(nums, 0, nums.size() - 1);
}
TreeNode* help(vector<int>& nums, int left, int right) {
//边界条件
if (left > right)
return NULL;
//创建根节点
int mid = (left + right)/2;
TreeNode* root = new TreeNode(nums[mid]);
//根据左子树的范围递归的去构造左子树
root->left = help(nums, left, mid - 1);
//根据右子树的范围递归的去构造右子树
root->right = help(nums, mid + 1, right);
return root;
}
};
# 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]: return self.help(nums, 0, len(nums) - 1) def help(self, nums, left, right): # 边界条件 if left > right: return None # 创建根节点 mid = (left + right) // 2 root = TreeNode(nums[mid]) # 根据左子树的范围递归的去构造左子树 root.left = self.help(nums, left, mid - 1) # 根据右子树的范围递归的去构造右子树 root.right = self.help(nums, mid + 1, right) return root
时间复杂度： 因为我们需要访问一遍数组中所有的元素，所以时间复杂度为O(n)，其中n 为数组中元素的个数。
空间复杂度： 我们需要创建n个节点，递归需要用到递归栈，递归的深度为logn，所以空间复杂度为O(n) + O(logn) = O(n)，其中n为数组中元素的个数。
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
