[백준 1991 node.js] 트리 순회

Jessie H·2022년 7월 2일
0

알고리즘 공부

목록 보기
15/20
post-thumbnail

백준 1991 트리 순회

문제 보러 가기

얼마 전에 프렙 코스에서 트리 자료구조를 배우고, 트리와 이진 탐색 트리를 직접 구현해보는 과제를 했었다. 배운 것을 응용해 보기 위해 트리 순회 문제를 풀어보았다.

첫째줄에는 트리 노드의 개수, 즉 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 부분에 결과값을 몰아넣는게 그거대로 약간 어려운 것 같다.

생각보다 어려웠던 포인트가 많아서 다시 풀어봐야겠다.

profile
코딩 공부 기록장

0개의 댓글