给你一个整数数组 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] 都是高度平衡二叉搜索树。
中间位置为根节点
/*** 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 _sortedArrayToBST(nums,0,nums.size()-1);}TreeNode*_sortedArrayToBST(vector<int>& nums,int left,int right){if(left>right){return nullptr;}int mid=(left+right)/2;TreeNode* root =new TreeNode(nums[mid]);root->left=_sortedArrayToBST(nums,left,mid-1);root->right=_sortedArrayToBST(nums,mid+1,right);return root;}
};