백준 1991 : 트리 순회 - javascript(트리)

문제 출처 

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

 

정답 코드 1

const input =require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift())

function solution(n, arr){
    const preOrderArr = []; 
    const inOrderArr = []; 
    const postOrderArr = []; 
   
    const tree = {}; 
    
    for(let i=0; i<arr.length;  i++){
      let [key, left, right] = arr[i].split(' '); 
        tree[key] = [left, right]
    }
    
    const rootNode = Object.keys(tree)[0]
    
    const preorder = (node, arr) => {
        if(node === '.') return; 
        let [left, right] = tree[node]
        arr.push(node)
        preorder(left, arr)
        preorder(right, arr)
    }
    const inorder = (node, arr) => {
         if(node === '.') return; 
        let [left, right] = tree[node]
        inorder(left, arr)
        arr.push(node)
        inorder(right, arr)
    }
    const postorder = (node, arr) => {
         if(node === '.') return; 
        let [left, right] = tree[node]
        postorder(left, arr)
        postorder(right, arr)
        arr.push(node)
    }
    
    preorder(rootNode , preOrderArr)
    inorder(rootNode , inOrderArr)
    postorder(rootNode , postOrderArr)
    
    console.log(preOrderArr.join(''))
    console.log(inOrderArr.join(''))
    console.log(postOrderArr.join(''))
}

solution(n, input)

정답 코드 2

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());