leetcode 刷题之路 64 Construct Binary Tree from Inorder and Postorder Traversal
2024-08-28 22:33:33
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
给出二叉树的中序遍历和后序遍历结果,恢复出二叉树。
后序遍历序列的最后一个元素值是二叉树的根节点的值。查找该元素在中序遍历序列中的位置mid,依据中序遍历和后序遍历性质。有:
位置mid曾经的序列部分为二叉树根节点左子树中序遍历的结果,得出该序列的长度n,则后序遍历序列前n个元素为二叉树根节点左子树后序遍历的结果。由这两个中序遍历和后序遍历子序列恢复出左子树。
位置mid以后的序列部分为二叉树根节点右子树中序遍历的结果,得出该序列的长度m,则后序遍历序列(除去最后一个元素)后m个元素为二叉树根节点右子树后序遍历的结果,由这两个中序遍历和后序遍历子序列恢复出左子树;
以上描写叙述中递归地引用了由中序遍历和后序遍历恢复子树的部分,因此程序也採用递归实现。
AC code:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ TreeNode *helper(vector<int> &inorder, int b1, int e1, vector<int> &postorder, int b2, int e2)
{
if (b1>e1)
return NULL;
int mid;
for (int i = b1; i <= e1; i++)
if (inorder[i] == postorder[e2])
{
mid = i;
break;
} TreeNode* root = new TreeNode(inorder[mid]);
root->left = helper(inorder, b1, mid - 1, postorder, b2, b2 + mid - b1-1);
root->right = helper(inorder, mid + 1, e1, postorder, b2 + mid-b1, e2 - 1);
return root;
}
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
};
最新文章
- [MapReduce] Google三驾马车:GFS、MapReduce和Bigtable
- markdown语法书
- springday04-go1
- java处理日期时间
- windows防火墙无法启动,服务不存在
- CentOS下Apache+SVN+LDAP的安装与配置
- php Laravel 框架 介绍及安装
- MVC实用架构设计:总体设计
- --save 和 --save-dev的区别
- Vue过渡效果之CSS过渡
- 关于Http协议,你必须要知道的
- 配置javaJDK环境
- 支持Linux系统的加密狗
- 【转载】“宇宙最强” IDE,Visual Studio 2019 正式发布
- https笔记【转】
- SSAS aggregation 的作用及其使用
- [学习笔记]Splay
- css3之transform属性实现div不定宽高垂直水平居中
- python 版本升级
- Android帧布局<;TabHost>;标签