leetcode 43:construct-binary-tree-from-inorder
2024-09-06 04:09:49
题目描述
给出一棵树的中序遍历和后序遍历,请构造这颗二叉树
注意:
保证给出的树中不存在重复的节点
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
示例1
输出
{1,2,3}
//不需要辅助函数,简单易懂
//后序遍历容器的最后一个数是根节点,中序遍历的根节点左边是左子树,右边是右子树,
//后序遍历左子树节点值相邻,右子树节点值也相邻。由后序遍历最后一个值将中序遍历分成
//左右两部分,再由这两部分的size将后序遍历分成左右两部分,递归即可
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.empty())
return NULL;
int nodeval=postorder[postorder.size()-1];
TreeNode* head=new TreeNode(nodeval);
vector<int>::iterator iter=find(inorder.begin(),inorder.end(),nodeval);
vector<int>leftin=vector<int>(inorder.begin(),iter);
vector<int>rightin=vector<int>(iter+1,inorder.end());
int left=leftin.size();
int right=rightin.size();
if(left>0)
{
vector<int>leftpo=vector<int>(postorder.begin(),postorder.begin()+left);
head->left=buildTree(leftin,leftpo);
}
if(right>0)
{
vector<int>rightpo=vector<int>(postorder.begin()+left,postorder.begin()+left+right);
head->right=buildTree(rightin,rightpo);
}
return head;
}
};
最新文章
- NSDateFormatter 相关理解
- Java第一个程序
- ssh无法登录linux服务器的解决办法
- 【UVa】11270 Tiling Dominoes
- [转] asp.net <;%%>;&;<;%#%>;&;<;%=%>;&;<;%@%>;&;<;%$%>;用法区别
- UI2_UIGesture
- csv文件与DataTable互相导入处理
- oracle11g 创建用户并授权
- 【转载】setjmp和longjmp函数使用详解
- Mysql语句的批量操作[修改]
- 解决Ubuntu不能连接xshell
- APUE-文件和目录(七)符号链接
- 自己编写服务启动脚本(一):functions文件详细分析和说明
- android studio签名
- AOP事务解决方案和分布式事务方案
- 简单了解 DLL中, .def 文件及C#调用C++方法
- Linux内核中的printf实现
- Python:Day13
- 安装oracle11g时遇到INS-13001环境不满足最低要求
- 数据契约(DataContract)里的DataMember特性