PTA A_1086 Tree Traversals Again
传送门：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, inorder;
void input(void)
{
int stack, top = -1, pi = 0, ii = 0;;
char s;
scanf("%d", &n);
for (int i = 0; i < 2 * n; i++)
{
scanf("%s", s);
if (strcmp(s, "Push"))
inorder = stack;
else
{
scanf("%d", preorder + pi);
stack[++top] = preorder;
}
}
}
int find(int target)
{
for (int i = 0; i < n; i++)
if (inorder == 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;
}
}
else
{
if (root->lchild)
insert(root->lchild, pos);
else
{
root->lchild = new BTNode;
root->lchild->data = inorder;
}
}
}
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;
for (int i = 1; i < n; i++)
insert(root, find(preorder));
print_postorder(root);
return 0;
}
页:
[1]