[백준] 1991 트리 순회 - JavaScript(NodeJS)

문제

1991번: 트리 순회

 

풀이

전위 순회, 중위 순회, 후위 순회를 순차적으로 실행하고 결과를 출력한다.

 

문제의 중요한 조건은 항상 A가 루트 노드이며 자식 노드가 없다면 .으로 표현된다.

 

입력에서 루트가 번호가 아닌 알파벳이 주어지므로, 객체를 이용하자.

 

node의 left, right 순으로 순회하도록 함수를 작성할 것이므로
어느 시점에서 노드를 출력하는가에 따라 전위, 중위, 후위 순회인지가 결정될 것이다.

 

 

코드로 바로 구현해본다.

코드

const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const tree = {};
  for (let i = 0; i < N; i++) {
    const [node, left, right] = input[i].split(" ");
    tree[node] = [left, right];  // tree의 키 값으로 노드를 저장하고, 값으로는 left, right가 담긴 배열을 저장한다.
  }

  let result = "";
  
  function preorder(node) {
    if (node === ".") return;
    const [lt, rt] = tree[node];
    result += node;
    preorder(lt);
    preorder(rt);
  }
  // 전위순회는 루트부터 기록을 시작하므로, 재귀의 맨 앞에서 우선 기록한다.

  function inorder(node) {
    if (node === ".") return;
    const [lt, rt] = tree[node];
    inorder(lt);
    result += node;
    inorder(rt);
  }
  // 중위순회는 왼쪽-루트-오른쪽 순이므로, 왼쪽의 재귀가 끝난 시점에서 기록한다.

  function postorder(node) {
    if (node === ".") return;
    const [lt, rt] = tree[node];
    postorder(lt);
    postorder(rt);
    result += node;
  }
  // 후위순회는 왼쪽-오른쪽-루트 순이므로, 왼쪽과 오른쪽 재귀가 끝난 시점에서 기록한다.

  preorder("A");
  result += "\n";
  inorder("A");
  result += "\n";
  postorder("A");

  return result;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

다음과 같이 출력하는 시점에 따라 순회가 달라진다.

 

바로 이해가 가지 않는다면, 트리를 직접 만들어서 손으로 그려보면서 하나씩 추적해보면 더 이해가 쉽다.