[백준] 5639 - 이진 검색 트리

최근 다녀온 삼성전자 DS SW직군 채용상담회에서 TREE와 Linked List문제 트랜트로 바뀌고 있다해서 많이 풀어보는 중

이 문제도 tree문제를 찾아서 풀던 중 기본부터 다지기 위해 시작하는 문제

일단 전위 순회로 입력되는 것을 EOF까지 입력받고, 이 데이터를 바탕으로 Tree를 역추적

그리고 후위 순회로 출력하며 동적할당된 노드를 삭제해주기만 하면 끝

#include <iostream>
#include <malloc.h>
#include <cstdio>
using namespace std;
 
typedef struct NODE {
    int num, ed;
    NODE *L;
    NODE *R;
}node;
 
int pre[10002], check[10002];
int st = -1;
 
node*makenewnode() {
    node*tmp = (node*)malloc(sizeof(node));
    tmp->num = 0; tmp->ed = 0;
    tmp->L = 0;
    tmp->R = 0;
    return tmp;
}
 
void insert(int pos, node *root, int num)
{
    node *tmp = root;
    tmp->num = num;
    tmp->L = makenewnode();
    tmp->R = makenewnode();
    int l = 0, r = 0;
    for (int i = pos; i <= st; i++)
    {
        if (check[i] == 1) break;
        if (pre[i] < num) { l = i; check[i] = 1; break; }
    }
    int i;
    if (l != 0) i = l + 1;
    else i = pos;
    for (; i <= st; i++)
    {
        if (check[i] == 1) break;
        if (pre[i] > num) { r = i; check[i] = 1; break; }
    }
 
    if (l != 0)
        insert(l + 1,tmp->L, pre[l]);
    else tmp->L->ed = 1;
    if (r != 0)
        insert(r + 1, tmp->R, pre[r]);
    else tmp->R->ed = 1;
}
 
void pos(node*root)
{
    node*tmp = root;
    if (tmp->ed) { free(tmp); return; }
    pos(root->L);
    pos(root->R);
    cout << tmp->num << endl;
    free(tmp);
}
 
int main(void)
{
    int n;
    node *root = makenewnode();
    while (scanf("%d", &n) != EOF)
    {
        pre[++st] = n;
    }
    check[0] = 1;
    insert(1, root, pre[0]);
    pos(root);
}