PAT 甲级 1086 Tree Traversals Again (25分)(先序中序链表建树,求后序)***重点复习

1086 Tree Traversals Again (25分)
 

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

PAT 甲级 1086 Tree Traversals Again (25分)(先序中序链表建树,求后序)***重点复习
Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2 lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

3 4 2 6 5 1

题意:

用栈的形式给出一棵二叉树的建立的顺序,求这棵二叉树的后序遍历

题解:

栈实现的是二叉树的中序遍历(左根右),而每次push入值的顺序是二叉树的前序遍历(根左右),所以该题可以用二叉树前序和中序转后序的方法做~

AC代码:

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int data;
node *left,*right;
};
vector<int>pre,in,post;
stack<int>s;
node *buildTree(vector<int>pre,vector<int>in,int pl,int pr,int il,int ir){
if(pl>pr || il>ir) return NULL;
int pos=-;
for(int i=il;i<=ir;i++){
if(in.at(i)==pre.at(pl)){
pos=i;
break;
}
}
node *root=new node();
//root->left=root->right=NULL;
root->data=pre.at(pl);
root->left=buildTree(pre,in,pl+,pl+pos-il,il,pos-);
root->right=buildTree(pre,in,pl+pos-il+,pr,pos+,ir);
return root;
}
void postorder(node *root){
if(root){
postorder(root->left);
postorder(root->right);
post.push_back(root->data);
}
}
int main(){
cin>>n;
pre.push_back(-);
in.push_back(-);
char c[];
int x;
for(int i=;i<=*n;i++){
cin>>c;
if(strcmp(c,"Push")==){
cin>>x;
s.push(x);
pre.push_back(x);
}else{
in.push_back(s.top());
s.pop();
}
}
node *root = buildTree(pre,in,,n,,n);
postorder(root);
for(int i=;i<post.size();i++){
cout<<post.at(i);
if(i!=post.size()-) cout<<" ";
}
return ;
}
上一篇:沙朗javascript(两)正则表达式


下一篇:常用的 Internet Browser adds-on/浏览器插件