C++代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node* lchild;
    node* rchild;
};

node* root = NULL;
const int Max = 50;
int pre[Max], in[Max];

void postorder(node* root)
{
    if(root)
    {
        postorder(root -> lchild);
        postorder(root -> rchild);
        printf("%d ", root -> data);
    }
}

node* build(int preL,int preR,int inL,int inR)
{
    if(preL > preR)return NULL;
    node* root = new node;
    root -> data = pre[preL];
    int k;
    for(k = inL; k <= inR; k ++)
    {
        if(in[k] == pre[preL])break;
    }
    root -> lchild = build(preL + 1, preL + k - inL, inL, k - 1);
    root -> rchild = build(preL + k - inL + 1, preR, k + 1, inR);
    return root;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> pre[i];
    for(int i = 1; i <= n; i ++)cin >> in[i];
    root = build(1, n, 1, n);
    postorder(root);
    return 0;
}