얼마 전에 프렙 코스에서 트리 자료구조를 배우고, 트리와 이진 탐색 트리를 직접 구현해보는 과제를 했었다. 배운 것을 응용해 보기 위해 트리 순회 문제를 풀어보았다.
첫째줄에는 트리 노드의 개수, 즉 2번째 줄부터 마지막줄까지 알파뱃을 입력받는 줄의 총 개수를 의미한다.
<script>
//입력 값 받기
//입력값의 총 집합 input
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
//입력값의 첫번째 값 = N
const N = +input[0];
//입력값의 두번째 ~ 마지막 값
const alphabet = input.slice(1);
let result = '';
for (let i = 0; i < N; i++) {
const treeNode = {};
//alphabet[i] = 두번째 줄부터 마지막 줄까지의 입력
const [node, left, right] = alphabet[i].split(' ');
//treeNode = {node: left, right, ...};
treeNode[node] = [left, right];
}
function preOrder (node) {
if (node === '.') {
return;
}
const [left, right] = treeNode[node];
result += node;
preOrder(left);
preOrder(right);
}
function inOrder (node) {
if (node === '.') {
return;
}
const [left, right] = treeNode[node];
result += node;
inOrder(left);
inOrder(right);
}
function postOrder (node) {
if (node === '.') {
return;
}
const [left, right] = treeNode(node);
postOrder(left);
postOrder(right);
result += node;
}
//root node는 A로 주어짐
preOrder('A');
result += '\n';
inOrder('A');
result += '\n'
postOrder('A');
result += '\n';
console.log(result);
</script>
가장 어려웠던 부분은 구조 할당 분해로 input의 두번째 ~ 마지막 줄까지를 코드로 나타내는 것이었다.
그리고 맨날 그냥 구현하는 것만 해보다가 root node가 A로 주어진다는 보니까 result 부분에 결과값을 몰아넣는게 그거대로 약간 어려운 것 같다.
생각보다 어려웠던 포인트가 많아서 다시 풀어봐야겠다.