PTA A_1086 Tree Traversals Again

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024

解：
前序遍历+中序遍历 恢复二叉树
Push的顺序是前序遍历
Pop的顺序是中序遍历

#include<cstdio>
#include<cstring>

typedef struct node{
    int data;
    struct node *lchild, *rchild;

    node(){
        lchild = rchild = NULL;
    }
} BTNode, *BTREE;

int n, num, preorder[35], inorder[35];

void input(void)
{
    int stack[35], top = -1, pi = 0, ii = 0;;
    char s[5];

    scanf("%d", &n);
    for (int i = 0; i < 2 * n; i++)
    {
        scanf("%s", s);

        if (strcmp(s, "Push"))
            inorder[ii++] = stack[top--];
        else
        {
            scanf("%d", preorder + pi);
            stack[++top] = preorder[pi++];
        }
    }
}

int find(int target)
{
    for (int i = 0; i < n; i++)
        if (inorder[i] == target)
            return i;
}

void insert(BTREE root, int pos)
{
    if (!root) return;

    int parents = find(root->data);

    if (pos > parents)
    {
        if (root->rchild)
            insert(root->rchild, pos);
        else
        {
            root->rchild = new BTNode;
            root->rchild->data = inorder[pos];
        }
    }
    else
    {
        if (root->lchild)
            insert(root->lchild, pos);
        else
        {
            root->lchild = new BTNode;
            root->lchild->data = inorder[pos];
        }
    }
}

void print_postorder(BTREE root)
{
    if (!root) return;

    print_postorder(root->lchild);
    print_postorder(root->rchild);
    printf("%d", root->data);

    if (++num < n) putchar(' ');
}

int main(void)
{
    input();

    BTREE root = new BTNode;
    root->data = preorder[0];
    for (int i = 1; i < n; i++)
        insert(root, find(preorder[i]));

    print_postorder(root);

    return 0;
}