算法-二叉树篇26-将有序数组转换为二叉搜索树
将有序数组转换为二叉搜索树
力扣题目链接
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
解题思路
很简单的遇到递归题目，对数组取半，然后构建中间节点作为该数组对应的树，然后左右两边切割数组递归下去。
题解
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0){
return nullptr;
}
if(nums.size() == 1){
TreeNode* temp = new TreeNode(nums[0]);
return temp;
}
int n = nums.size() / 2;
vector<int> arr1(nums.begin(), nums.begin() + n);
vector<int> arr2(nums.begin() + n + 1, nums.end());
TreeNode* temp = new TreeNode(nums[n]);
temp->left = sortedArrayToBST(arr1);
temp->right = sortedArrayToBST(arr2);
return temp;
}
};