[백준] 트리의 순회 (2263번)

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

예제 입력 1 복사

3 1 2 3 1 3 2

예제 출력 1 복사

2 1 3

---

인오더와 포스트오더를 이용해서 프리오더를 출력하는 문제이다.

포스트오더는 leftNode를 방문한 후, rightNode를 방문하고 currentNode를 visit하기때문에 제일 마지막 값이 root가 된다. 

인오더는 left, current, right 노드 순으로 방문하므로 포스트오더에서 알아낸 루트노드의 왼쪽은 leftChild, 오른쪽은 rightChild가 된다. 

예제를 예로 들면 인오더 : 1 2 3 , 포스트오더 : 1 3 2에서 포스트오더의 마지막인 2가 루트이므로 인오더의 2 왼쪽 값인 1은 leftChild, 3은 rightChild가 되는 것이다.

이런식으로 인오더의 마지막 노드 정보를 활용해서 left, right 노드를 만들어주면 된다.

 

makeTree함수에서 원래는 void로 current data를 그냥 cout으로 출력해도 정답을 구할 수 있지만 기왕 만드는거 트리를 만들고 싶어서 Node를 struct로 만들고 포인터를 이용해 root를 루트로 트리를 만들었다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%88%9C%ED%9A%8C%20(2263%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> inOrder, postOrder;
int pos[100001]; // inOrder의 각 값의 위치
struct Node {
	int data;
	Node* leftNode;
	Node* rightNode;
	Node() {
		data = -1;
		leftNode = NULL;
		rightNode = NULL;
	}
};

Node* makeTree(int inStart, int inEnd, int poStart, int poEnd) {
	if (inStart > inEnd || poStart > poEnd) return NULL;
	Node* cur = new Node();
	cur->data = postOrder[poEnd];

	int rootPos = pos[cur->data];
	cur->leftNode = makeTree(inStart, rootPos - 1, poStart, poStart + (rootPos - inStart) - 1);
	cur->rightNode = makeTree(rootPos + 1, inEnd, poStart + (rootPos - inStart), poEnd - 1);

	return cur;	
}

void preOrder(Node* cur) {
	if (cur == NULL) return;
	cout << cur->data << " ";
	preOrder(cur->leftNode);
	preOrder(cur->rightNode);
}

int main()
{
	cin >> N;
	for (int tmp, i = 1; i <= N; i++) {
		cin >> tmp;
		inOrder.push_back(tmp);
	}
	for (int tmp, i = 1; i <= N; i++) {
		cin >> tmp;
		postOrder.push_back(tmp);
	}
	for (int i = 0; i < N; i++)
		pos[inOrder[i]] = i;
	Node *root;
	root = makeTree(0, N - 1, 0, N - 1);

	preOrder(root);
}