[백준 1991 - Node.js] 트리 순회

🔗 문제 링크

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

✏️ 풀이

const [N, ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const nodes = input.map(v => v.split(' '));

class Tree {
  constructor(value) {
    this.value = value;
    this.leftNode = null;
    this.rightNode = null;
  }

  traversePreOrder(curNode = this) {
    if (!curNode) {
      return '';
    }
    const leftNodes = this.traversePreOrder(curNode.leftNode);
    const rightNodes = this.traversePreOrder(curNode.rightNode);
    return curNode.value + leftNodes + rightNodes;
  }

  traverseInOrder(curNode = this) {
    if (!curNode) {
      return '';
    }
    const leftNodes = this.traverseInOrder(curNode.leftNode);
    const rightNodes = this.traverseInOrder(curNode.rightNode);
    return leftNodes + curNode.value + rightNodes;
  }

  traversePostOrder(curNode = this) {
    if (!curNode) {
      return '';
    }
    const leftNodes = this.traversePostOrder(curNode.leftNode);
    const rightNodes = this.traversePostOrder(curNode.rightNode);
    return leftNodes + rightNodes + curNode.value;
  }
}

const trees = Array
  .from({ length: N }, (_, i) => new Tree(String.fromCharCode(i + 65)))
  .reduce((acc, tree) => {
    acc[tree.value] = tree;
    return acc;
  }, {});

nodes.forEach(([node, left, right]) => {
  if (left !== '.') {
    trees[node].leftNode = trees[left];
  }
  if (right !== '.') {
    trees[node].rightNode = trees[right];
  }
});

console.log(trees.A.traversePreOrder());
console.log(trees.A.traverseInOrder());
console.log(trees.A.traversePostOrder());

재귀를 통해 트리 순회를 구현하였다.

 

 

const [N, ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const nodes = input.map(v => v.split(' '));
const trees = nodes.reduce((acc, [node, left, right]) => {
    acc[node] = { left, right };
    return acc;
}, {});

const traversePreOrder = (node) => {
    if (node === '.') {
        return '';
    }
    const { left, right } = trees[node];
    return node + traversePreOrder(left) + traversePreOrder(right);
};

const traverseInOrder = (node) => {
    if (node === '.') {
        return '';
    }
    const { left, right } = trees[node];
    return traverseInOrder(left) + node + traverseInOrder(right);
};

const traversePostOrder = (node) => {
    if (node === '.') {
        return '';
    }
    const { left, right } = trees[node];
    return traversePostOrder(left) + traversePostOrder(right) + node;
};

console.log(traversePreOrder('A'));
console.log(traverseInOrder('A'));
console.log(traversePostOrder('A'));

클래스를 사용하여 트리 자료구조를 구현하지 않아도 이렇게 하면 더 간결하게 해결할 수 있다.