PAT (Advanced) 1086. Tree Traversals Again (25)

원제Tree Traversals Again (25)
문제 해결 방법:
실제로 입고 순서는 앞의 순서, 출고 순서는 중간 순서이다. 그러면 두 개의 순서가 있으면 두 갈래 나무를 직접 구성할 수 있고 후속의 순서도 바로 얻을 수 있다.
코드는 다음과 같습니다.

#include
#include
#include
#include
using namespace std;
const int maxn = 30 + 5;
struct Node
{
    int id;
    Node* lchild, *rchild, *parent;
    Node(){id = 0; lchild = NULL; rchild = NULL; parent = NULL;}
};

int preOrder[maxn], inOrder[maxn];

void build(Node* &root, int l1, int r1, int l2, int r2)
{
    if(l1 > r1) return ;
    root = new Node();
    root->id = preOrder[l1];
    int k;
    for(k = l2; k <= r2; k++)
        if(inOrder[k] == preOrder[l1]) break;
    int c = k - l2;
    build(root->lchild, l1+1, l1+c, l2, k-1);
    build(root->rchild, l1+c+1, r1, k+1, r2);
}


void postOrder(Node* root, int &first)
{
    if(root->lchild != NULL)
        postOrder(root->lchild, first);
    if(root->rchild != NULL)
        postOrder(root->rchild, first);
    if(first) {printf("%d", root->id); first = 0;}
    else printf(" %d", root->id);
}

int main()
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        stack sta;
        int cnt = 0, cPre = 0, cIn = 0;
        while(cnt < n)
        {
            char cmd[5];
            int x;
            scanf("%s", cmd);
            if(cmd[1] == 'u')
            {
                scanf("%d", &x);
                sta.push(x);
                preOrder[cPre++] = x;
            }
            else
            {
                inOrder[cIn++] = sta.top();
                sta.pop();
                cnt++;
            }
        }
        Node* root = NULL;
        build(root, 0, n-1, 0, n-1);
        int first = 1;
        postOrder(root, first);
        printf("
");
    }
    return 0;
}