【hiho一下 第十周】后序遍历
2024-08-28 07:30:02
【题目链接】:http://hihocoder.com/problemset/problem/1049
【题意】
【题解】
前序遍历的第一个节点;
肯定是整颗树的头结点;
然后在中序遍历中;
得到这个树的左子树和右子树;
然后再分别得到左子树和右子树的前序遍历;
递归处理就好;
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
int root,l[30],r[30];
string s1,s2;
int dfs(string s1,string s2)
{
if (s1==""||s2=="") return 0;
char t = s1[0];
int x = t-'A'+1;
int pos = s2.find(t,0);
int llen = pos,rlen = s2.size()-llen-1;
l[x] = dfs(s1.substr(1,llen),s2.substr(0,llen));
r[x] = dfs(s1.substr(1+llen,rlen),s2.substr(pos+1,rlen));
return x;
}
void dfs(int x)
{
if (x==0) return;
dfs(l[x]);dfs(r[x]);
char t = x+'A'-1;
cout << t;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
cin >> s1 >> s2;
root = dfs(s1,s2);
dfs(root);
cout << endl;
return 0;
}
最新文章
- 大数据技术Hadoop入门理论系列之一----hadoop生态圈介绍
- iOS----------使用 Xcode6或Xcode7配置.pch文件
- BZOJ2124: 等差子序列
- java中线程分两种,守护线程和用户线程。
- 前端自动化工具 -- grunt 使用简介
- please tell me the error about java Graphics
- 简单实例讲解linux的module模块编译步骤
- c++读取文件内容并保存到二维数组
- oracle 选择最频繁出现之前,5文章数据
- 自定义MVP .net框架
- sed用法小结
- ural1553 Caves and Tunnels
- IOS 动画的两种方式
- const char *p;和char * const p的区别
- IE浏览器清除缓存没用
- [POJ 3635] Full Tank?
- 异常 - 虚拟机初始化错误 - Error occurred during initialization of VM
- Servlet(四):转发与重定向、路径问题
- nagios系列(一)centos6.5环境部署nagios服务端
- laravel中redis队列的使用