PAT Advance 1020
题目:
1020. Tree Traversals (25)
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
注意点:
代码中红色代码尤其需要注意,不设置为空的话会出错。
程序:
#include<iostream>
#include<queue>
using namespace std;
typedef struct _Node
{
int num;
struct _Node *lchild;
struct _Node *rchild;
}Node, *PNode;
int t1[1001],t2[1001];
int n;
int getPosition(int a){
int i;
for(i=1;i<=n;i++)
if(a == t2[i])
return i;
}
void createTree(PNode &node, int i, int j, int len){
if(len<=0){
return ;
}
node = new Node;
node->num = t1[i];
node->lchild = NULL;
node->rchild = NULL;
int m = getPosition(t1[i]);
createTree(node->lchild,i-len+m-j,j,m-j);//m-j:左子树len,len-1-(m-j):右子树len
createTree(node->rchild,i-1,m+1,len-1-m+j);
}
void PreTravelTree(PNode pn) //前序递归遍历
{
if(pn){
cout<<pn->num<<" "<<endl;
PreTravelTree(pn->lchild);
PreTravelTree(pn->rchild);
}
}
int main()
{
int i;
int r[100];
queue<PNode> q;
cin>>n;
for(i=1;i<=n;i++)
cin>>t1[i];
for(i=1;i<=n;i++)
cin>>t2[i];
PNode root = NULL,temp;
createTree(root,n,1,n);
q.push(root);
i=0;
while(!q.empty()){
temp = q.front();
q.pop();
r[i] = temp->num;
i++;
if(temp->lchild!=NULL)
q.push(temp->lchild);
if(temp->rchild!=NULL)
q.push(temp->rchild);
}
cout<<r[0];
for(i=1;i<n;i++)
cout<<" "<<r[i];
cout<<endl;
return 0;
}
最新文章
- Solr环境搭建过程中遇到的问题
- Erlang第二课 ---- bit串
- 解高次同余方程 (A^x=B(mod C),0<;=x<;C)Baby Step Giant Step算法
- Android 滑动效果入门篇(二)—— Gallery
- sql语句的分类
- js数组与对象的一些区别。
- C++部分术语(Terms)
- AngularJs开发——指令与控制器间的通信
- pig的一些实例(我常用的语法)
- springboot2 pagehelper 使用笔记
- 第三方登陆——QQ登陆详解
- C#常用的命名规则汇总
- Hibernate4
- celery --分布式任务队列
- 恢复Intellij idea删除的文件
- maven eclipse操作
- VC++中多字节字符集和Unicode之间的互换
- (八)git更改提交操作
- ACM -- 算法小结(六)逆波兰表达式
- Verilog_Day3
热门文章
- iOS 购物车动画
- python hello wlord
- FreeMarker静态化文件解决SEO推广问题
- pandas DataFrame 数据处理常用操作
- .Net 程序员面试 C# 语言篇 (回答Scott Hanselman的问题)
- Sql學習資源
- 通道符和xargs命令
- atitit.js&#160;javascript&#160;调用c#&#160;java&#160;php后台语言api&#160;html5交互的原理与总结p97
- python操作sqlserver
- 新标准C++程序设计读书笔记_类和对象