PAT-1020 Tree Traversals

传送门

题意

根据中序遍历和后序遍历，输出层次遍历。

思路

后序遍历的最后一个结点是根结点，在中序遍历中找到该结点，在该结点左边的则是左子树，右边的则是右子树。此时问题就变成了左右子树两个子问题。所以该题用递归写即可。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

int postorder[35], inorder[35];
vector<int> g[35];

void build(int u, int idx, int left, int right){   //u是父亲结点， idx是后序遍历的第idx结点，left和right是子树的结点范围
    if(left > right)    return;
    for(int i=left; i<=right; i++){   //找到当前子树的根结点
        if(inorder[i] == postorder[idx]){
            g[u].push_back(inorder[i]);
            build(postorder[idx], idx-1, left, i-1);  //递归左子树
            build(postorder[idx], idx-1, i+1, right); //递归右子树
            return;
        }
    }
    build(u, idx-1, left, right);    //如果没有找到，那么找后序遍历的下一个结点
}


int main(){
    //freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++)  scanf("%d", &postorder[i]);
    for(int i=1; i<=n; i++)  scanf("%d", &inorder[i]);
    int pos;
    for(int i=1;i<=n;i++){  //找到根结点
        if(inorder[i] == postorder[n]){
            pos = i;
            break;
        }
    }
    build(postorder[n], n-1, 1, pos-1);   //递归左子树
    build(postorder[n], n-1, pos+1, n);   //递归右子树
    queue<int> q;
    q.push(postorder[n]);
    while(!q.empty()){   //层次遍历输出
        int s = q.front();
        q.pop();
        for(int i=0; i<g[s].size(); i++){
            q.push(g[s][i]);
        }
        printf("%d", s);
        if(!q.empty())  printf(" ");
    }
    printf("
");
    return 0;
}