더블릿_이진트리방문1

PREORDER로 주어진 트리 정보를 이용해

POSTORDER를 출력하는 문제였다. 

노드의 제한은 20개 였다. 

노드의 자식이 없는 경우에 -1을 제공하는 친절한 문제였다. 

처음에는 -1이라는 정보를 이용해 완전이진트리를 구조화하는 트리배열을 만들어도 될까 고민했다. 

(2*N + 1, 2*N + 2)

노드 최대 개수는 20개였으므로 최악의 테스트케이스에서 2의 21승의 노드 배열이 필요했다. 

비주얼스튜디오 환경에서 배열을 100만개 이상 전역으로 선언하는 것은 아무 문제가 없었고, 실제로 어느 테스트케이스에서도 100만개 이상의 순회를 할 필요는 절대 없다고 판단했다. 일렬로 쭉 늘어뜨린 트리의 형태여도 재귀적으로 42번정도만 수행하면 된다. 

그래서 입력 받은 PREORDER정보를 완전이진트리 배열로 만들어주었다. 

테스트케이스에서 

5 3 11 7 -1 -1 2 -1 -1 -1 8 13 -1 -1 4 -1 1 -1 -1

이면 

완전이진트리배열

node[32] = 

5, 3, 8, 11, -1, 13, 4, 7, 2, 0, 0, -1, -1, -1, 1, -1, -1, -1, -1, ......

이런식으로 만들어진다. 

그 다음에는 완전이진트리배열을 이용해 재귀적으로 postorder를 사용해주면 된다. 

void postorder(int node_index){ if (node[node_index] == -1 || node[node_index] == 0){ return; } postorder(2 * node_index + 1); postorder(2 * node_index + 2); cout << node[node_index] << " "; }