A1086 Tree Traversals Again (25分

/*
题意：
1、push为先序，pop为后序，然后唯一确定一棵树

解题：
1、其实就是给先序和中序，求出后续
写法固定

learn && wrong:
1、格式不对

*/

#include <iostream>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;

/*
1、结构体
2、合成树
3、后序遍历

*/

const int maxn = 50;
int preorder[maxn], inorder[maxn],postorder[maxn];
int n;

struct node {
    int data;
    node* lchild;
    node* rchild;
};

node* create(int preL, int preR, int inL, int inR) {
    if (inL > inR) {    //递归边界
        return NULL;
    }

    node* root = new node;
    root->data = preorder[preL];

    int i;
    for (i = inL;i < inR;i++) { //找到根节点
        if (inorder[i] == preorder[preL]) { //!!!又是preL这里错
            break;
        }
    }

    int leftnum = i - inL ; //      ！！！

    //先序的左子树 preL + 1,preL + leftnum, 中序inL, inL + i - 1
    root->lchild = create(preL + 1, preL + leftnum, inL, i - 1);

    //先序的右子树 preL + leftnum + 1,preR, 中序 i + 1，
    root->rchild = create(preL + leftnum + 1, preR, i + 1, inR);

    return root;
}


//后续遍历
int num = 0;
void post(node* root) {
    if (root == NULL) {
        return;
    }
    post(root->lchild);
    post(root->rchild);
    printf("%d", root->data);
    num++;  //！！！顺序颠倒
    if (num < n) {
        printf(" ");
        
    }
}

int main()
{
    cin >> n;
    char str[5];
    stack<int> st;
    int x, preindex = 0, inindex = 0;   //入栈元素，先序序列位置及中序序列位置
    for (int i = 0;i < 2 * n;i++) {
        cin >> str;
        if (strcmp(str, "Push") == 0) {
            cin >> x;
            preorder[preindex++] = x;
            st.push(x);
        }
        else {
            inorder[inindex++] = st.top();
            st.pop();
        }
    }
    node* root = create(0, n - 1, 0, n - 1);
    post(root);

    return 0;
}