pat甲级 A1020 Tree Traversals (25分)

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072

题目分析：

树的遍历。通过后序序列 + 中序序列得到层序序列。题目给出树的节点最多有30个，若使用满二叉树的数组存储该树，则所开辟的数组大小可能达到2的31次方。测试发现当数组大小num = 2500即可，所以测试案列中无那种特别奇怪的单支树存在。

参考代码：

#include<iostream>
#include<vector>
using namespace std;
const int num = 1e5;
vector<int> post, in, level(num, -1);
void Order(int root,int il,int ih,int index)
{
    if(ih<il) return;
    int i = il; //Llen, Rlen;
    level[index]=post[root];
    while(i <= ih && in[i] != post[root]) i++;//Llen=i-il;  Rlen=ih-i;
    Order(root - ih + i - 1, il, i-1, 2*index);
    Order(root-1, i+1, ih, 2*index+1);  //root = ih, 若将order()的第一个参数改成i + 1出现错误。
}

int main()
{
    int i,N,cnt=0;
    cin>>N;
    post.resize(N);
    in.resize(N);
    for(i=0;i<N;i++) cin>>post[i];
    for(i=0;i<N;i++) cin>>in[i];
    Order(N-1, 0, N-1,1);
    for(i=0;i<num;i++)
        if(level[i]!=-1){
            cnt++; cout<<level[i];
            if(cnt<N) cout<<" ";
        }
    return 0;
}

下面考虑正常的通过后序，中序建树，然后层序遍历输出结果。已知通过中序和前序/后序/层序，都可以唯一确定一棵二叉树。

#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 50 ;
struct tree{
    int data;
    tree* left;
    tree* right;
};

int pre[maxn], in[maxn], post[maxn];   //前，中，后序序列
int n, cnt = 0; //cnt记录已经输出的节点数目

tree* create(int postl, int posth, int inl, int inh){ //通过后序，中序建树，返回二叉树的根节点。
    if(postl > posth) return NULL;
    tree* root = new tree; //tree node;
    root->data = post[posth];
    int i = inl;
    while(i <= inh && in[i] != post[posth]) i++;   //根据后序以及中序找出根节点。
    int numleft = i - inl;              //左子树的节点个数
    root->left = create(postl, postl + numleft - 1, inl, i - 1);    //虽然第一次postl = inl，但postl + numleft -1 不能写成i-1。同理，postl + numleft 不能写成i。因为第二次遍历根节点的右子树时，inl != postl。
    root->right = create(postl + numleft, posth - 1, i + 1, inh);
    return root;
}

void level(tree* root){// 层序输出节点
    queue <tree*> q;  //队列中存地址
    q.push(root);
    while(!q.empty()){
        tree* now = q.front(); //取出队首元素。
        q.pop();
        printf("%d", now->data);
        cnt++; //输出节点数目加一；
        if(cnt < n) printf(" ");
        if(now->left) q.push(now->left);
        if(now->right) q.push(now->right);
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d", &post[i]);
    for(int i = 0; i < n; i++) scanf("%d", &in[i]);
    tree* root = create(0, n-1, 0, n - 1);
    level(root);
    return 0;
}