백준 1991 트리 순회

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const solution = (input) => {
  const n = +input.shift();
  const tree = {};
  for (let [node, left, right] of input.map((e) => e.split(" "))) {
    tree[node] = [left, right];
  }
  let result = "";
  // 전위 순회
  const preorder = (node) => {
    if (node === ".") return;
    const [lt, rt] = tree[node];
    result += node;
    preorder(lt);
    preorder(rt);
  };
  // 중위 순회
  const inorder = (node) => {
    if (node === ".") return;
    const [lt, rt] = tree[node];
    inorder(lt);
    result += node;
    inorder(rt);
  };
  // 후위 순회
  const 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;
};

console.log(solution(input));

• 백트래킹을 이용하고, 정답을 나타낼 result 문자열에 더하는 타이밍에 따라 전위, 중위, 후위 순회가 나뉜다.
• 인프런 강의에 비슷한 문제가 있다.