每日一题-108. 将有序数组转换为二叉搜索树

题目描述题目分析解决方案

题目描述

108. 将有序数组转换为二叉搜索树 难度：简单 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / -3 9 / / -10 5 通过次数91,465提交次数125,311 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 来源：力扣（LeetCode）

题目分析

看到树.第一反应就应该是递归.

解决方案

代码如下。修改middle的计算公式可以获得不同可能的结果。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return subSort(nums,0,nums.size()-1); } //ruturn subtree TreeNode* subSort(vector<int>& nums,const int beging,const int end){ if(beging>end) return NULL; if(beging==end) return (new TreeNode(nums.at(beging))); int middle=(beging+end)>>1; TreeNode* root; root=new TreeNode(nums.at(middle)); root->left=subSort(nums,beging,middle-1); root->right=subSort(nums,middle+1,end); return root; } };

时间复杂度为O(n)，空间复杂度为O(n)。