이진 트리를 이용한 문제이다. 먼저 전위 순회로 입력되는 값을 트리를 구현하여 저장해주었다. 그 후 후위 순회로 값들을 차례로 출력해주었다.
처음에는 배열로 노드를 구성하여 이를 순회하며 출력해주었는데 아웃바운드가 발생했다. 이유는 값이 많아질수록 배열의 요구 크기가 점점 너무 커지기때문에 범위 밖 접근이 발생한 것이다. 이를 해결하기 위해 트리를 직접 구현해주었다. 이 과정이 시간이 오래 걸렸다.
#include <iostream>
using namespace std;
struct Node {
int n;
Node* left;
Node* right;
};
Node* setNode(Node* node, int n) {
if (node == NULL) {
node = new Node;
node->n = n;
node->left = NULL;
node->right = NULL;
}
else if (n < node->n) {
node->left = setNode(node->left, n);
}
else {
node->right = setNode(node->right, n);
}
return node;
}
void printNode(Node* node) {
if (node->left != NULL)
printNode(node->left);
if (node->right != NULL)
printNode(node->right);
cout << node->n << endl;
}
void solution(Node* node) {
printNode(node);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
Node* A = NULL;
int a;
while (cin >> a) {
if (a == EOF) break;
A = setNode(A, a);
}
solution(A);
return 0;
}