LeetCode——Construct Binary Tree from Inorder and Postorder Traversal
2024-08-27 23:25:19
Question
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution
参考:http://www.cnblogs.com/zhonghuasong/p/7096300.html
Code
/**
* 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0)
return NULL;
return ConstructTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
TreeNode* ConstructTree(vector<int>& inorder, vector<int>& postorder,
int in_start, int in_end, int post_start, int post_end) {
int rootValue = postorder[post_end];
TreeNode* root = new TreeNode(rootValue);
if (in_start == in_end) {
if (post_start == post_end && inorder[in_start] == postorder[post_start])
return root;
}
int rootIn = in_start;
while (rootIn <= in_end && inorder[rootIn] != rootValue)
rootIn++;
int leftPostLength = rootIn - in_start;
if (leftPostLength > 0) {
// 注意起点和终点的写法
root->left = ConstructTree(inorder, postorder, in_start, rootIn - 1, post_start, post_start + leftPostLength - 1);
}
if (leftPostLength < in_end - in_start) {
root->right = ConstructTree(inorder, postorder, rootIn + 1, in_end, post_start + leftPostLength, post_end - 1);
}
return root;
}
};
最新文章
- 【GoLang】GoLang 微服务、开源库等参考资料
- 前端编码规范(4)—— CSS 和 Sass (SCSS) 规范
- 菜鸟学四轴控制器之3:数字积分法DDA实现直线插补
- mysql开启日志
- URAL 2068 Game of Nuts (博弈)
- Programming pages of Jasper Neumann
- 纯CSS制作冒泡提示框
- iOS 非ARC基本内存管理系列 2-多对象内存管理(3) 利用@property来自动管理内存
- jquery easy ui 学习 (2) customtools window
- HybridApp开发准备工作——WebView
- undefined reference to `_sbrk&#39;, `_write&#39;, `_lseek&#39;, `_read&#39;
- 201521123106《java程序设计》第三周学习总结
- MySql的虚拟机和Xshell5的连接过程
- Python 为何能坐稳 AI 时代头牌语言
- trigger click 和 click 的区别??
- struts2-剩余
- 利用反射获取数据列+emit生成属性+单例模式
- Activiti工作流数据库表详细介绍
- BZOJ3237 AHOI2013连通图(线段树分治+并查集)
- Linux查看操作系统版本命令
热门文章
- R-ArcGIS探秘(1)安装以及Sample执行
- NetBeans执行项目报错
- nginx 在浏览器端保持cookie 一致
- activity通过流程实例id动态获取流程图并展示在jsp页面上
- IIS无法连接LocalDb,怎么办?
- EasyGBS国标流媒体服务器GB28181国标方案安装使用文档
- Error: unable to connect to node rabbit@10: nodedown 修改hostname后异常
- MFC重绘原理的关键理解
- [Erlang危机](5.1.3)进程
- ORACLE中RECORD、VARRAY、TABLE的使用具体解释