THU2015 fall 2-3 Rebuild
4099 단어 rebuildMOOC두 갈래 나무가 두루 다니다앞 순서
THU2015 fall 2-3 Rebuild
묘사
어떤 두 갈래 나무의 n개 노드는 이미 [1,n] 내의 정수로 번호를 매겼다.현재 이 두 갈래 트리의 선순 역행 시퀀스와 중순 역행 시퀀스를 지정하여 대응하는 후순 역행 시퀀스를 출력합니다.
입력
첫 번째 행위는 한 수 n이다.
두 번째, 세 번째 줄, 즉 이미 알고 있는 선순, 중순은 서열을 훑어보고 숫자 사이는 빈칸으로 구분된다.
출력
단 한 줄.
만약에 주어진 선순, 중속 역행 서열이 어떤 두 갈래 나무에 대응하면 그 후 역행 서열을 출력하고 숫자 사이를 빈칸으로 구분합니다.그렇지 않으면 -1을 출력합니다.
샘플 1 입력
5
1 2 4 5 3
4 2 5 1 3
출력 샘플 1
4 5 2 3 1
샘플 2 입력
4
2 3 1 4
4 2 1 3
출력 샘플 2
-1
샘플 3 입력
8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8
출력 샘플 3
4 1 2 7 8 6 3 5
제한
1 <= n <= 500000, n은 정수
입력과 출력의 반복 서열은 모두 [1,n] 내 정수의 한 배열이며, 정수 사이는 모두 빈칸으로 구분된다.
시간: 1sec
공간: 256MB
코드는 다음과 같습니다.#include <stdio.h>
#include <stdlib.h>
const int SZ = 1 << 20; // IO buff
struct fastio{
char inbuf[SZ];
char outbuf[SZ];
fastio(){
setvbuf(stdin, inbuf, _IOFBF, SZ);
setvbuf(stdout, outbuf, _IOFBF, SZ);
}
}io;
#define N 500000
struct Node
{
Node *lchild, *rchild;
int x;
}Tree[N];
int loc;
//int pro[N], mid[N];
int count = 0;
Node *create()
{
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}
Node *buildTree(int *pro, int *mid, int x1, int y1, int x2, int y2)
{
Node *root = create();
root->x = pro[x1];
int loc_root;
int flag = 1;
for (int i = x2; i <= y2; i++)
if (mid[i] == pro[x1]) //
{
loc_root = i;
flag = 0;
count++;
break;
}
if (flag) return NULL;
if (loc_root != x2)
root->lchild = buildTree(pro, mid, x1 + 1, x1 + loc_root - x2, x2, loc_root - 1);
if (loc_root != y2)
root->rchild = buildTree(pro, mid, x1 + loc_root - x2 + 1, y1, loc_root + 1, y2);
return root;
}
void postOrder(Node *Tree)
{
if (Tree->lchild != NULL) postOrder(Tree->lchild);
if (Tree->rchild != NULL) postOrder(Tree->rchild);
printf("%d ", Tree->x);
}
int main()
{
int n;
scanf("%d", &n);
int *pro = (int *)malloc((n + 1) * sizeof(int));
int *mid = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i < n; i++)
scanf("%d", pro + i);
for (int i = 0; i < n; i++)
scanf("%d", mid + i);
Node *Tree = buildTree(pro, mid, 0, n-1, 0, n-1);
if (count != n) printf("-1");
else postOrder(Tree);
printf("
");
//system("pause");
free(pro);
free(mid);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
04-트리 6.Huffman Codes (30)
시간 제한
메모리 제한
코드 길이 제한
For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a',...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
5
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
4
2 3 1 4
4 2 1 3
-1
8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8
4 1 2 7 8 6 3 5
#include <stdio.h>
#include <stdlib.h>
const int SZ = 1 << 20; // IO buff
struct fastio{
char inbuf[SZ];
char outbuf[SZ];
fastio(){
setvbuf(stdin, inbuf, _IOFBF, SZ);
setvbuf(stdout, outbuf, _IOFBF, SZ);
}
}io;
#define N 500000
struct Node
{
Node *lchild, *rchild;
int x;
}Tree[N];
int loc;
//int pro[N], mid[N];
int count = 0;
Node *create()
{
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}
Node *buildTree(int *pro, int *mid, int x1, int y1, int x2, int y2)
{
Node *root = create();
root->x = pro[x1];
int loc_root;
int flag = 1;
for (int i = x2; i <= y2; i++)
if (mid[i] == pro[x1]) //
{
loc_root = i;
flag = 0;
count++;
break;
}
if (flag) return NULL;
if (loc_root != x2)
root->lchild = buildTree(pro, mid, x1 + 1, x1 + loc_root - x2, x2, loc_root - 1);
if (loc_root != y2)
root->rchild = buildTree(pro, mid, x1 + loc_root - x2 + 1, y1, loc_root + 1, y2);
return root;
}
void postOrder(Node *Tree)
{
if (Tree->lchild != NULL) postOrder(Tree->lchild);
if (Tree->rchild != NULL) postOrder(Tree->rchild);
printf("%d ", Tree->x);
}
int main()
{
int n;
scanf("%d", &n);
int *pro = (int *)malloc((n + 1) * sizeof(int));
int *mid = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i < n; i++)
scanf("%d", pro + i);
for (int i = 0; i < n; i++)
scanf("%d", mid + i);
Node *Tree = buildTree(pro, mid, 0, n-1, 0, n-1);
if (count != n) printf("-1");
else postOrder(Tree);
printf("
");
//system("pause");
free(pro);
free(mid);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
04-트리 6.Huffman Codes (30)시간 제한 메모리 제한 코드 길이 제한 For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a',...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.