【LeetCode】106. Construct Binary Tree from Inorder and Postorder Traversal
2024-08-27 22:49:39
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
根据定义,后序遍历postorder的最后一个元素为根。
由于元素不重复,通过根可以讲中序遍历inorder划分为左子树和右子树。
递归下去即可求解。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return Helper(inorder, , inorder.size()-, postorder, , postorder.size()-);
}
TreeNode* Helper(vector<int>& inorder, int begin1, int end1, vector<int>& postorder, int begin2, int end2)
{
if(begin1 > end1)
return NULL;
else if(begin1 == end1)
return new TreeNode(inorder[begin1]); TreeNode* root = new TreeNode(postorder[end2]);
int i = begin1;
for(; i <= end1; i ++)
{
if(inorder[i] == postorder[end2])
break;
}
int leftlen = i-begin1; root->left = Helper(inorder, begin1, begin1+leftlen-, postorder, begin2, begin2+leftlen-);
root->right = Helper(inorder, begin1+leftlen+, end1, postorder, begin2+leftlen, end2-);
return root;
}
};
最新文章
- JS核心系列:理解 new 的运行机制
- Java I/O and NIO [reproduced]
- Python Day10
- css样式—字体垂直、水平居中
- 【转】关于KDD Cup '99 数据集的警告,希望从事相关工作的伙伴注意
- C++ socket编程
- 201521123027 <;java程序设计>;第八周学习总结
- Android Stdio 如何自定义生成APK的名称
- cookie的设置和获取
- python 一篇搞定所有的异常处理
- bzoj3122 [SDOI2013]随机数生成器
- 使用Eclipse创建动态的web工程
- WIN10中DOCKER的安装
- day014 模块
- the project already contains a form or module named pcm001怎麼解決
- ORACLE 锁表处理,解锁释放session
- 基于QProbe创建基本Android图像处理框架
- 目标检测--Selective Search for Object Recognition(IJCV, 2013)
- ASP.NET MVC异步验证是如何工作的01,jQuery的验证方式、错误信息提示、validate方法的背后
- 大型Web 网站 Asp.net Session过期你怎么办
热门文章
- Java实现-2016百度秋招(颜色反转、相似字符串)
- JS之RegExp对象(一)
- warning: suggest parentheses around assignment used as truth value
- Git 报错:git - error: RPC failed; curl 18 transfer closed with outstanding read data remaining 解决方案
- vc预处理
- java Class的 getSuperclass与getGenericSuperclass区别
- ECMA-262,第 5 版 最新 JavaScript 规范
- 怎么删除桌面右键";打开好桌道壁纸";
- 一道有序洗牌的笔试题,阿里\UC等都用过
- windows10 Sqlserver卸载 指定账户不存在