PAT1020 (已知中序，后序遍历转前序遍历)

已知后序与中序输出前序（先序）：
后序：3, 4, 2, 6, 5, 1（左右根）
中序：3, 2, 4, 1, 6, 5（左根右）

已知一棵二叉树，输出前，中，后时我们采用递归的方式。同样也应该利用递归的思想：

对于后序来说，最后一个节点肯定为根。在中序中可以找到左子树的个数，那么就可以在后序中找到左子树的根；同理也可以找到右子树。

void pre(int root, int start, int end) {

    if(start > end) return ;

    int i = start;

    while(i < end && in[i] != post[root]) i++;

    printf("%d ", post[root]);

    pre(root -  - end + i, start, i - );

    pre(root - , i + , end);

}

如果想要按照层次输出数，那么我们可以增加一个index变量，来存储结点。根节点为0，左子树为index*2+1, 右子树为index*2+2，那么我们按顺序输出不是-1的节点即可

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

vector<int>lever(,-),post,in;

int n;

void pre(int root,int start,int end,int index)

{

    if(start>end)

        return;

    int i=start;

    while(i<end&&in[i]!=post[root])

        i++;

    lever[index]=post[root];

    pre(root-end+i-,start,i-,index*+);

    pre(root-,i+,end,index*+);

}

int main()

{

    scanf("%d",&n);

    post.resize(n+);

    in.resize(n+);

    for(int i=;i<=n;i++)

        scanf("%d",&post[i]);

    for(int i=;i<+n;i++)

        scanf("%d",&in[i]);

    pre(n,,n,);

    int cnt=;

    for(int i=;i<lever.size();i++)

    {

        if(lever[i]!=-)

        {

            cnt++;

            if(cnt==n)

            {

                printf("%d\n",lever[i]);

                break;

            }

            else

                printf("%d ",lever[i]);

        }

    }

}