一开始用的第一种解法,但是大测试内存超了,所以不能迭代的时候不能每次返回一个TreeNode,而是需要建立一个引用,每一次修改引用可以节省空间。时间复杂度来说都是一样的。
class Solution { public: TreeNode *build(vector<int> num, int start, int end){ if (start > end) return NULL; int mid = (start + end) / 2; TreeNode *tmpRoot = new TreeNode(num[mid]); tmpRoot->left = build(num, start, mid-1); tmpRoot->right = build(num, mid+1, end); return tmpRoot; } TreeNode *sortedArrayToBST(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function if (num.size() == 0) return NULL; int start = 0; int end = num.size()-1; return build(num,start,end); } }; class Solution { public: void buildTree(vector<int> &num, int start, int end, TreeNode* &tmpRoot) { if (start > end) return; int mid = (start+end)/2; tmpRoot = new TreeNode(num[mid]); buildTree(num, start, mid-1, tmpRoot->left); buildTree(num, mid+1, end, tmpRoot->right); } TreeNode *sortedArrayToBST(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function TreeNode* root = NULL; int start = 0; int end = num.size() - 1; buildTree(num, start, end, root); return root; } };
原文链接: https://www.cnblogs.com/tanghulu321/archive/2013/04/15/3021379.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/84760
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!