[C++] 백준 2263번: 트리의 순회

 

2263번: 트리의 순회

지난 1학기 자료구조 중간고사에서 유사한 문제가 출제 됐었다.

in-order와 post-order를 주고 이를 만족하는 트리 그리기였나 그랬다.

하지만 충분한 시간 동안 고민해 본 결과, 어떻게 풀어야 할 지 몰라서 다음 블로그를 참고했다.

백준 2263번 트리의 순회

 

직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다.  후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 해당 트리의 루트입니다.  그리고 중위 순회를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 나온 후에는 오른쪽 부분트리입니다.  따라서, 이 성질을 이용해서 재귀함수를 호출하면 AC를 받을 수 있습니다.
출처: https://jaimemin.tistory.com/1156 [꾸준함]

 

블로그에서 설명해 준 것처럼 직접 그려 보면서 규칙을 찾았으면 금방 찾았을지도 모른다.

다음부터는 문제 풀이를 위해 펜과 종이를 적극적으로 사용해가며 노력해야겠다.

아무튼, 위 설명대로 코드를 작성하기 시작했다. 처음 제출한 코드는 다음과 같다.

inorder, preorder 함수는 검토를 위해 작성한 함수다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int n;
vector<int> inorder, postorder;

typedef struct Node* NodePtr;
typedef struct Node {
	int value;
	NodePtr* child;
} Node;

void buildGraph(NodePtr parent, int in_left, int in_right, int post_left, int post_right) {
	// add child(here) to parent
	int root = postorder[post_right];
	NodePtr node = (NodePtr)malloc(sizeof(Node));
	node->child = (NodePtr*)malloc(sizeof(Node) * 2);
	node->child[0] = node->child[1] = NULL;
	node->value = root;
	if (parent->child[0] == NULL)
		parent->child[0] = node;
	else
		parent->child[1] = node;
	// final condition
	if (in_right <= in_left)
		return;
	// find root index
	int root_idx = in_left;
	while (inorder[root_idx] != root)
		root_idx++;
	int child_post_right = post_left;
	if (root_idx != in_right) {
		while (postorder[child_post_right] != inorder[root_idx + 1])
			child_post_right++;
		// its left child
		buildGraph(node, in_left, root_idx - 1, post_left, child_post_right - 1);
		// its right child
		buildGraph(node, root_idx + 1, in_right, child_post_right, post_right - 1);
	}
	else // no right child
		buildGraph(node, in_left, root_idx - 1, post_left, post_right - 1);
}

void printInorder(NodePtr root) {
	if (root == NULL)
		return;
	printInorder(root->child[0]);
	cout << root->value << ' ';
	printInorder(root->child[1]);
}

void printPostorder(NodePtr root) {
	if (root == NULL)
		return;
	printPostorder(root->child[0]);
	printPostorder(root->child[1]);
	cout << root->value << ' ';
}

void printPreorder(NodePtr root) {
	if (root == NULL)
		return;
	cout << root->value << ' ';
	printPreorder(root->child[0]);
	printPreorder(root->child[1]);
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	cin >> n;
	inorder = vector<int>(n);
	postorder = vector<int>(n);

	for (int i = 0; i < n; i++)
		cin >> inorder[i];
	for (int i = 0; i < n; i++)
		cin >> postorder[i];

	NodePtr head = (NodePtr)malloc(sizeof(Node));
	head->child = (NodePtr*)malloc(sizeof(Node) * 2);
	head->child[0] = head->child[1] = NULL;
	buildGraph(head, 0, n - 1, 0, n - 1);

	//printInorder(head->child[0]);
	//cout << EL;
	//printPostorder(head->child[0]);
	//cout << EL;
	printPreorder(head->child[0]);
	cout << EL;

	return 0;
}

하지만 틀렸다고 나와서 질문 검색을 해보니, complete tree가 아니었을 때를 고려하지 못 했다.

사실 위 코드는 complete binary tree가 아니면 제대로 작동하지 않는다.

그래서 아래와 같이 코드를 고쳤다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int n;
vector<int> inorder, postorder;

typedef struct Node* NodePtr;
typedef struct Node {
	int value;
	NodePtr* child;
} Node;

void buildGraph(NodePtr parent, int side, int in_left, int in_right, int post_left, int post_right) {
	// add child(here) to parent
	int root = postorder[post_right];
	NodePtr node = (NodePtr)malloc(sizeof(Node));
	node->child = (NodePtr*)malloc(sizeof(Node) * 2);
	node->child[0] = node->child[1] = NULL;
	node->value = root;
	switch (side) {
	case 0:
		parent->child[0] = node;
		break;
	case 1:
		parent->child[1] = node;
		break;
	}
	// final condition
	if (in_right <= in_left)
		return;
	// find root index
	int root_idx = in_left;
	while (inorder[root_idx] != root)
		root_idx++;
	if (root_idx == in_right) // no right child
		buildGraph(node, 0, in_left, root_idx - 1, post_left, post_right - 1);
	else if (root_idx == in_left) // no left child
		buildGraph(node, 1, in_left + 1, in_right, post_left, post_right - 1);
	else {
		int child_post_right = post_left + root_idx - in_left;
		// its left child
		buildGraph(node, 0, in_left, root_idx - 1, post_left, child_post_right - 1);
		// its right child
		buildGraph(node, 1, root_idx + 1, in_right, child_post_right, post_right - 1);
	}
}

void printInorder(NodePtr root) {
	if (root == NULL)
		return;
	printInorder(root->child[0]);
	cout << root->value << ' ';
	printInorder(root->child[1]);
}

void printPostorder(NodePtr root) {
	if (root == NULL)
		return;
	printPostorder(root->child[0]);
	printPostorder(root->child[1]);
	cout << root->value << ' ';
}

void printPreorder(NodePtr root) {
	if (root == NULL)
		return;
	cout << root->value << ' ';
	printPreorder(root->child[0]);
	printPreorder(root->child[1]);
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	cin >> n;
	inorder = vector<int>(n);
	postorder = vector<int>(n);

	for (int i = 0; i < n; i++)
		cin >> inorder[i];
	for (int i = 0; i < n; i++)
		cin >> postorder[i];

	NodePtr head = (NodePtr)malloc(sizeof(Node));
	head->child = (NodePtr*)malloc(sizeof(Node) * 2);
	head->child[0] = head->child[1] = NULL;
	buildGraph(head, 0,	0, n - 1, 0, n - 1);

	//printInorder(head->child[0]);
	//cout << EL;
	//printPostorder(head->child[0]);
	//cout << EL;
	printPreorder(head->child[0]);
	cout << EL;

	return 0;
}

함수 인수에 부모의 어느 방향의 자식으로서 호출됐는지를 나타내어 부모 자식 중 적절한 위치에 추가할 수 있도록 했다.

해당 영역에서 루트가 inorder에서 어디에 위치하냐에 따라서 왼쪽, 오른쪽 방향으로 자식을 호출했다.

지금 생각해보니 동적할당 해주고 메모리 해제를 안 해줬다. 주의해야지.

else if에서 else를 적지 않아 한참 헤멨다.

디버깅도 계속 해보고 중간마다 출력도 해보고 그러다가 나중에서야 발견했다.

문제가 생기면 코드를 침착하게 다시 살펴보는 습관을 가져야겠다.