博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode_654. Maximum Binary Tree
阅读量:6222 次
发布时间:2019-06-21

本文共 2166 字,大约阅读时间需要 7 分钟。

https://leetcode.com/problems/maximum-binary-tree/

给定数组A,假设A[i]为数组最大值,创建根节点将其值赋为A[i],然后递归地用A[0,i-1]创建左子树,用A[i+1,n]创建右子树。


 

使用vector的assign函数,该函数的特性:

Any elements held in the container before the call are destroyed and replaced by newly constructed elements (no assignments of elements take place).

This causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.


 

class Solution{public:    TreeNode* constructMaximumBinaryTree(vector
& nums) { vector
::iterator maxiter,iter=nums.begin(); int maxn=INT_MIN,len=nums.size(); while(iter!=nums.end()) { if(*iter>maxn) { maxn=*iter; maxiter=iter; } iter++; } vector
lnums,rnums; TreeNode *node = new TreeNode(maxn); if(maxiter!=nums.begin()) { lnums.assign(nums.begin(),maxiter); node->left = constructMaximumBinaryTree(lnums); } if(maxiter!=nums.end()-1) { rnums.assign(maxiter+1,nums.end()); node->right = constructMaximumBinaryTree(rnums); } return node; }};

 

因为assign函数的特性是,每次给vector赋值都会自动销毁原先vector中的对象,虽然这里使用的是c++内置类型,但是多少还是会有开销。所以又写了一个不使用assign的版本。

class Solution{public:    TreeNode* constructMaximumBinaryTree(vector
& nums) { return buildTree(nums, 0, nums.size()-1); } TreeNode* buildTree(vector
& nums, int l, int r) { if(l > r) return NULL; if(l == r) { TreeNode* node = new TreeNode(nums[l]); return node; } int max_n = INT_MIN, max_index = l; for(int i=l; i<=r ; i++) if(nums[i]>max_n) { max_n = nums[i]; max_index = i; } TreeNode* root = new TreeNode(max_n); root->left = buildTree(nums, l, max_index-1); root->right = buildTree(nums, max_index+1, r); return root; }};

 

转载于:https://www.cnblogs.com/jasonlixuetao/p/10582782.html

你可能感兴趣的文章
jquery的checkbox,radio,select等方法总结
查看>>
Linux coredump
查看>>
Ubuntu 10.04安装水晶(Mercury)无线网卡驱动
查看>>
Myeclipes快捷键
查看>>
我的友情链接
查看>>
ToRPC:一个双向RPC的Python实现
查看>>
我的友情链接
查看>>
nginx在reload时候报错invalid PID number
查看>>
神经网络和深度学习-第二周神经网络基础-第二节:Logistic回归
查看>>
Myeclipse代码提示及如何设置自动提示
查看>>
c/c++中保留两位有效数字
查看>>
ElasticSearch 2 (32) - 信息聚合系列之范围限定
查看>>
VS2010远程调试C#程序
查看>>
[MicroPython]TurniBit开发板DIY自动窗帘模拟系统
查看>>
由String类的Split方法所遇到的两个问题
查看>>
Python3.4 12306 2015年3月验证码识别
查看>>
从Handler.post(Runnable r)再一次梳理Android的消息机制(以及handler的内存泄露)
查看>>
windows查看端口占用
查看>>
strongswan ikev2 server on ubuntu 14.04
查看>>
Yii用ajax实现无刷新检索更新CListView数据
查看>>