백준 1991 트리 순회

문제

알고리즘, 트리와 관련되어있는 곳이라면 항상 나오는 단골손님 이진 트리에 대해서 전위순회, 중위순회, 후위순회한 결과를 출력하면 된다.

순회는 기본적으로 계속 파고들어가면서 위치에 따라 순서만 다르게 입력되는 형태기 때문에 dfs를 이용하여 풀면 된다.

예제를 보고 처음에는 배열의 인덱스로 순회를 시켜줄 수 있겠다 싶었는데 그렇게 되면 A-B-D로 가는 루트에서 D의 인덱스를 찾기가 어려워진다. D를 찾기 위해서는 순차적으로 다시 배열을 검사해야 할 필요성이 있기 때문에 시간이 더 걸리겠다고 생각헀다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const tree = {};
rest.forEach((r) => {
  const [a, b, c] = r.split(" ");
  tree[a] = [b, c];
});

따라서 처음에는 Object로 모든 tree의 구조를 각 노드를 키값으로 가지고 왼, 오 노드만을 0,1 인덱스의 리스트로 가지는 형태로 자료구조를 바꿔주었다.

let pre = "";
let inn = "";
let post = "";
 
function traversal(i, order) {
  if (i === ".") return;
  if (order === "pre") pre += i;
  if (tree[i][0]) {
    traversal(tree[i][0], order);
  }
  if (order === "in") inn += i;
  if (tree[i][1]) {
    traversal(tree[i][1], order);
  }
  if (order === "post") post += i;
}

이후에는 그냥 트리를 순회하면서 처음에 설정한 order에 맞게 문자열을 추가하는 순서를 조정해주면 된다.

맨처음에는 preorder,inorder,postorder 따로 함수를 만드려고 했는데, 기본적인 재귀 구조는 똑같으므로 굳이 필요성을 느끼지 않았다. 그래서 이러한 구조로 만든 뒤에 각각 order를 구별하여 한번씩 실행시켜 주었다.

function traversal(i) {
  if (i === ".") return;
  pre += i;
  if (tree[i][0]) {
    traversal(tree[i][0]);
  }
  inn += i;
  if (tree[i][1]) {
    traversal(tree[i][1]);
  }
  post += i;
}

근데 다시 생각해보니 그냥 따로따로 문자열에 추가시켜주면 굳이 순서를 나누지 않아도 될 것 같았다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const tree = {};
rest.forEach((r) => {
  const [a, b, c] = r.split(" ");
  tree[a] = [b, c];
});
let pre = "";
let inn = "";
let post = "";
 
function traversal(i) {
  if (i === ".") return;
  pre += i;
  if (tree[i][0]) {
    traversal(tree[i][0]);
  }
  inn += i;
  if (tree[i][1]) {
    traversal(tree[i][1]);
  }
  post += i;
}
 
traversal("A");
 
console.log(pre);
console.log(inn);
console.log(post);
 

그렇게 나온 코드

위에가 함수를 한번만 실행시킨거고 아래가 함수를 각 순서별로 order 인자를 넣어 세번 실행시킨 건데 시간이 같다..