seunghyun Note
[백준] 1991번 : 트리 순회 with JS 본문
728x90
반응형
링크 : https://www.acmicpc.net/problem/1991
문제 풀이
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
아직 트리에 대한 이해도가 많이 부족한 거 같다.
굳이 class를 만들어서 풀 필요가 없었다.
또한 순회에 대한 재귀가 아직 이해가 되지 않아 아래의 링크를 참고했다. (이것을 본 순간 순회의 규칙을 찾고 이해하기 쉬웠다!!)
tree를 객체에 저장하고 root Node를 기준으로 left, right를 설정해준다. (자동으로 연결됨)
const fs = require("fs");
//const n = fs.readFileSync("예제.txt").toString().trim().split("\n").map(Number);
//const [n, ...arr] = fs.readFileSync("예제.txt").toString();
///dev/stdin
const [n, ...arr] = fs.readFileSync("예제.txt").toString().trim().split("\n");
const tree = {};
let result = "";
for (let i = 0; i < arr.length; i++) {
let [node, left, right] = arr[i].split(" ");
tree[node] = [left, right];
// console.log(tree[node]);
}
function preorder(node) {
if (node === ".") return;
const [left, right] = tree[node];
result += node;
preorder(left);
preorder(right);
}
function inorder(node) {
if (node === ".") return;
const [left, right] = tree[node];
inorder(left);
result += node;
inorder(right);
}
function postorder(node) {
if (node === ".") return;
const [left, right] = tree[node];
postorder(left);
postorder(right);
result += node;
}
preorder("A");
result += "\n";
inorder("A");
result += "\n";
postorder("A");
console.log(result);
728x90
반응형
'코딩테스트 > 백준' 카테고리의 다른 글
백준 1181 : 단어 정렬 (0) | 2024.03.06 |
---|---|
최대힙 (0) | 2024.02.26 |
[백준] 1316번 : 그룹 단어 체커 with JS (0) | 2024.01.25 |
[백준] 28279번 : 덱 2 with JS (0) | 2024.01.25 |
[백준] 11866번 : 요세푸스 문제 0 with JS (1) | 2024.01.24 |