2263번 트리의 순회

https://www.acmicpc.net/problem/2263

1. 고민의 과정

post order를 통해 루트 노드를 구할 수 있음을 확인하였다.

루트 노드를 찾았으니 in - order에서 왼쪽 서브트리와 오른쪽 서브트리를
찾을 수 있다.

이제 array와 brray에서 왼쪽 서브트리를 찾으면 다시 거기서 그 서브트리의 루트노드를 찾아서 이를 부모노드와 연결하는 것이 내 아이디어이다.

2. 내 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int array[100000];
int brray[100000];

typedef struct node
{
	int data;
	struct node* left;
	struct node* right;
}Node;

Node* MakeTree(int a_l, int a_r, int b_l, int b_r)
{
	if (a_l > a_r) return NULL;//트리가 존재하지 않을 조건

	int i;
	int route;

	Node* node = malloc(sizeof(Node));
	node->left = NULL;
	node->right = NULL;
	node->data = brray[b_r];

	for (i = a_l; i <= a_r; i++)
	{
		if (array[i] == brray[b_r])
		{
			route = i;
			break;
		}
	}

	node->left = MakeTree(a_l, route - 1, b_l, b_l + (route - a_l) - 1);
	node->right = MakeTree(route + 1, a_r, b_l + (route - a_l), b_r - 1);//왼쪽 서브트리의 노드 개수는 (route - a_l -1) 개로 같으므로 위와 같이 할 수 있다.

	return node;
}

void PreOrder(Node* cur)//pre order 함수
{
	if (cur == NULL) return;
	printf("%d ", cur->data);
	PreOrder(cur->left);
	PreOrder(cur->right);
}

 

int main()
{
	int i, n;
	Node* Route;

	scanf("%d", &n);
	
	for (i = 0; i < n; i++)
	{
		scanf("%d", &array[i]);
	}

	for (i = 0; i < n; i++)
	{
		scanf("%d", &brray[i]);
	}

	Route = MakeTree(0, n - 1, 0, n - 1);

	PreOrder(Route);

	return 0;
}

3. 다른 알고리즘 고민

내 시간은 1260ms 인데 상위권들은 44ms이길래 어떻게 저럴 수 있을까 생각해보았다.

아마 트리를 만들지 않고 그냥 pre order를 구할 수 있는 규칙을 찾아낸 것일텐데 그 규칙을 고민해보기로 했다.