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

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

 

전위 순회로 나온 노드의 키들로 순서대로 새로운 트리를 만들면 동일한 트리가 나온다.

입력으로 새로운 트리를 만들어서 후위 순회한 결과를 출력하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

struct Node {
	Node(int key) :key(key) {}
	Node* parent = nullptr;
	Node* left = nullptr;
	Node* right = nullptr;
	int key;
};

Node* root = nullptr;

void Insert(int key) {
	Node* newNode = new Node(key);
	if (root == nullptr) {
		root = newNode;
		return;
	}

	Node* parent = nullptr;
	Node* curr = root;

	while (curr) {
		parent = curr;
		if (curr->key > key)
			curr = curr->left;
		else
			curr = curr->right;
	}

	newNode->parent = parent;
	if (parent->key < key)
		parent->right = newNode;
	else
		parent->left = newNode;
}

void Print(Node* node) {
	if (node == nullptr)
		return;

	Print(node->left);
	Print(node->right);
	cout << node->key << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int key;
	while (cin >> key) {
		Insert(key);
	}
	Print(root);
};