欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT甲级 1086 Tree Traversals Again 二叉树已知前序、中序求后序

程序员文章站 2022-06-11 15:11:21
...

PAT甲级 1086 Tree Traversals Again 二叉树已知前序、中序求后序
PAT甲级 1086 Tree Traversals Again 二叉树已知前序、中序求后序

Solution:

push的顺序即为前序
pop出栈的顺序即为中序
根据前序、中序求后序

代码如下:

//二叉树已知前序、中序求后序
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

int pre[35],in[35];
int n;
stack<int> s;
vector<int> post(n);

void post_traversal(int root,int start,int ends){//后序打印
  if(start>ends){
    return;
  }
  int i=start;
  while(i<ends&&in[i]!=pre[root]){//找到中序序列中根结点的位置
    i++;
  }
  post_traversal(root+1,start,i-1);//遍历左子树
  post_traversal(root+1+i-start,i+1,ends);//遍历右子树
  post.push_back(pre[root]);
}

int main(){
    cin>>n;
    string command;
    int ans1=0,ans2=0;
    int key;
    for(int i=0;i<=2*n-1;i++){
        cin>>command;
        if(command=="Push"){
            cin>>key;
            pre[ans1++]=key;
            s.push(key);
        }else if(command=="Pop"){
            in[ans2++]=s.top();
            s.pop();
        }
    }

    post_traversal(0,0,n-1);
    for(int i=0;i<post.size();i++){
        if(i!=post.size()-1){
            cout<<post[i]<<" ";
        }else{
            cout<<post[i];
        }
    }
    return 0;
}

相关标签: PAT甲级