大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天在网上看到一份阿里应届生薪资的抽样统计，主要是算法岗和开发岗，基本上月薪都达到了20k以上，一些算法岗的ssp居然给到了38k。虽说大家都在吐槽难找工作，但是这些大企业还是很舍得给钱的。
评论区不少其他行业的网友认为这开的太高了，凭啥互联网行业薪资这么高。也有行业内的网友说，凌晨刚下班，他觉得每一分钱都是应得的，三个月后他可能还嫌给的少了。虽说互联网的薪资水平相对较高，这跟它的工作强度是分不开的，大部分时候相应的时薪也不见得特别高。
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;
}
};
python代码
# 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为数组中元素的个数。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
