글 읽기 - 반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

이 문제는 반례가 있는 질문 글이 없네요. post에서의 마지막 원소가 해당 트리의 루트 노드가 된다는 점과, in에서 루트 노드를 기준으로 좌측이 좌측 서브트리, 우측이 우측 서브트리가 된다는 점을 이용했습니다. 원소가 1개일 때도, 아래 2가지 경우에도 잘 작동되었습니다.

6
4 2 5 1 3 6
4 5 2 6 3 1
---------------
1 2 4 5 3 6

11
8 4 2 5 9 1 10 6 3 7 11
8 4 9 5 2 10 6 11 7 3 1
-----------------------------
1 2 4 8 5 9 3 6 10 7 11

#include <stdio.h>
#include <stdlib.h>
struct nodes {
	long long int a;
	struct nodes *left;
	struct nodes *right;
};
long long int *in, *post, n;
void pre(struct nodes *node);
void lcheck(struct nodes *node, long long int inf, long long int inr, long long int postf, long long int postr);
void rcheck(struct nodes *node, long long int inf, long long int inr, long long int postf, long long int postr);
int main(void)
{
	long long int i;
	struct nodes *node;
	scanf("%lld", &n);
	in = (long long int *)calloc(n, sizeof(long long int));
	post = (long long int *)calloc(n, sizeof(long long int));
	for (i = 0; i < n; i++)
		scanf("%lld", &in[i]);
	for (i = 0; i < n; i++)
		scanf("%lld", &post[i]);
	node = (struct nodes *)calloc(1, sizeof(struct nodes));
	node->a = post[n - 1];
	for (i = 0; i < n; i++)
		if (in[i] == node->a)
			break;
	lcheck(node, 0, i - 1, 0, i - 1);
	rcheck(node, i + 1, n - 1, i, n - 2);
	pre(node);
	printf("\n");
	return 0;
}
void lcheck(struct nodes *node, long long int inf, long long int inr, long long int postf, long long int postr)
{
	long long int i;
	struct nodes *nnode;
	if (inf == inr)
	{
		nnode = (struct nodes *)calloc(1, sizeof(struct nodes));
		node->left = nnode;
		nnode->a = in[inf];
		return;
	}
	for (i = inf; i <= inr; i++)
	{
		if (in[i] == post[postr])
		{
			nnode = (struct nodes *)calloc(1, sizeof(struct nodes));
			node->left = nnode;
			nnode->a = post[postr];
			lcheck(nnode, inf, i - 1, postf, i - 1);
			rcheck(nnode, i + 1, inr, i, postr - 1);
		}
	}
}
void rcheck(struct nodes *node, long long int inf, long long int inr, long long int postf, long long int postr)
{
	long long int i;
	struct nodes *nnode;
	if (inf == inr)
	{
		nnode = (struct nodes *)calloc(1, sizeof(struct nodes));
		node->right = nnode;
		nnode->a = post[postr];
		return;
	}
	for (i = inf; i <= inr; i++)
	{
		if (in[i] == post[postr])
		{
			nnode = (struct nodes *)calloc(1, sizeof(struct nodes));
			node->right = nnode;
			nnode->a = post[postr];
			lcheck(nnode, inf, i - 1, postf, i - 2);
			rcheck(nnode, i + 1, inr, i, postr - 1);
		}
	}
}
void pre(struct nodes *node)
{
	printf("%lld", node->a);
	if (node->left != NULL)
	{
		printf(" ");
		pre(node->left);
	}
	if (node->right != NULL)
	{
		printf(" ");
		pre(node->right);
	}
}

blanka 3년 전 1

오래된 글이지만 본문의 두번째 예시가 있을 수 없는 데이터입니다.

/ \

2 3

/ \ / \

4 5 6 7

| | | |

8 9 10 11

이런 트리를 의도하신 것 같은데 그러면 데이터는 아래와 같고,

11
8 4 2 9 5 1 10 6 3 11 7
8 4 9 5 2 10 6 11 7 3 1

답은

1 2 4 8 5 9 3 6 10 7 11

입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

blanka 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말