[C++] 백준 5639번: 이진 검색 트리

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

5639번: 이진 검색 트리

예제를 직접 손으로 그려보면서 정답을 유추했다. BST이므로 전위순회 결과를 보면 트리가 어떤 모양인지 알 수 있는 것 같다. 그래서 전위순회 결과 순서대로 BST를 만들어주고, 이를 다시 후위순회하여 출력했더니 AC를 받았다. 간단한 문제였다.

#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"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
typedef struct Node {
	int key;
	Node* left;
	Node* right;
} Node;
typedef Node* NodePtr;
NodePtr tree;

/* define debug functions here */

/* define functions here */
NodePtr create_node(int key) {
	NodePtr root = (NodePtr)malloc(sizeof(Node));
	root->left = root->right = nullptr;
	root->key = key;
	return root;
}

NodePtr insert_key(NodePtr root, int key) {
	if (root == nullptr) {
		root = create_node(key);
		return root;
	}
	if (key < root->key)
		root->left = insert_key(root->left, key);
	else if (key > root->key)
		root-> right = insert_key(root->right, key);
	return root;
}

void print_postorder(NodePtr tree) {
	if (tree == nullptr)
		return;
	print_postorder(tree->left);
	print_postorder(tree->right);
	cout << tree->key << EL;
}

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

	/* Write input codes here */
	tree = nullptr;
	while (!cin.eof()) {
		int key;
		cin >> key;
		tree = insert_key(tree, key);
	}

	/* Write solution codes here */
	print_postorder(tree);

	return 0;
}