1086 Tree Traversals Again (25 分)(二叉树…

2018-12-09 11:18:12来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

用栈来模拟一棵二叉树的先序遍历和中序遍历过程,求这棵二叉树的后序遍历

由题棵知道:push是先序遍历

                      pop是中序遍历

#include<bits/stdc++.h>

using namespace std;
vector<int>pre;
vector<int>in;
vector<int>vec;
const int N=50;
int pre1[N];
int in1[N];
void print(int l1,int r1,int l2,int r2)
{
    if(l1>r1||l2>r2) return;
    int mid=l2;
    while(in[mid]!=pre[l1]) mid++;
    print(l1+1,l1+mid-l2,l2,mid-1);
    print(l1+mid-l2+1,r1,mid+1,r2);
    vec.push_back(pre[l1]);
}
int main()
{
    int n;
    scanf("%d",&n);
    stack<int>st;
    for(int i=0;i<2*n;i++){
        char s[20];
        scanf("%s",s);
        if(strcmp(s,"Push")==0){
            int num;
            scanf("%d",&num);
            st.push(num);
            pre.push_back(num);
        }
        else{
            int t=st.top();
            st.pop();
            in.push_back(t);
        }
    }

    print(0,n-1,0,n-1);
    for(int i=0;i<vec.size();i++){
        if(i) printf(" ");
        printf("%d",vec[i]);
    }
    printf("\n");
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1004 Counting Leaves (30 分)(树的遍历)

下一篇:[C++] 化学方程式的格式化算法