Node.js) 백준 1068번: 트리

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

1068번: 트리

node로 풀다가 런타임에러....

내가 입력을 잘못받았나?,, 부터 시작해서 자료구조/알고리즘 외적인 부분?? 에 빠져서 시간낭비. 

 

이 문제 주의할 점. 

1. 이진트리가 아니다. 

2. 0번 노드가 루트노드가 아니다. 

3. 루트노드가 삭제될 수 있다. 

 

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const node = input[1].trim().split(' ').map(Number);
const del = +input[2]

class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  insert(p, data) {
    let newNode = new Node(data);
    if (p == -1) {
      this.root = newNode;
    } else {
      let parent = this.find(p);
      newNode.parent = parent;
      parent.children.push(newNode)
    }
  }

  find(data) {
    const q = [this.root]
    while (q.length > 0) {
      let nowNode = q.shift();
      if (nowNode.data == data) {
        return nowNode;
      } else {
        nowNode.children.forEach(node => {
          q.push(node);
        });
      }
    }
  }

  delete(data) {
    if (data == this.root.data) {
      this.root = null;
      return;
    }
    let delNode = this.find(data);
    let parent = delNode.parent;
    delNode.parent = null;
    parent.children = parent.children.filter(v => v.data != data);
  }

  findLeaf() {
    if (this.root == null) {
      return 0;
    }
    let cnt = 0;
    let q = [this.root];
    while (q.length > 0) {
      let nowNode = q.shift();
      if (nowNode.children.length == 0) {
        cnt++;
      } else {
        nowNode.children.forEach(node => {
          q.push(node);
        });
      }
    }
    return cnt;
  }

}


let tree = new Tree();

const nodeObj = node.map((v, i) => {
  return {
    p: v,
    data: i,
  }
}).sort((a, b) => a.p - b.p);

let q = [nodeObj[0]];

while (q.length > 0) {
  let { p, data } = q.shift();
  tree.insert(p, data);
  nodeObj.forEach(v => {
    if (v.p == data) {
      q.push(v)
    }
  })
}


tree.delete(del)
const answer = tree.findLeaf();
console.log(answer)