Node.js) 백준 2250번: 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

 

class Node {
  left = null;
  right = null;
  level = null;
  location = null;
  parent = null;
  constructor(value) {
    this.value = value;
  }

  setLevel(level) {
    this.level = level;
  }

  setLeft(left) {
    this.left = left;
  }

  setRight(right) {
    this.right = right;
  }

  setParent(parent) {
    this.parent = parent;
  }
  setLocation(loc) {
    this.location = loc;
  }
}

class Tree {
  pointer = new Array(N).fill(null);
  parents = new Array(N).fill(null);
  location = 1;
  root = null;
  level = 0;
  result;
  constructor(nodes) {
    this.nodes = nodes;
  }

  createNode() {
    nodes.forEach((node) => {
      const [v, l, r] = node;
      const newNode = new Node(v);
      this.pointer[v] = newNode;
      if (l != -2) this.parents[l] = v;
      if (r != -2) this.parents[r] = v;
    });
  }

  findRoot() {
    for (let i = 0; i < N; i++) {
      if (this.parents[i] == null) {
        this.root = this.pointer[i];
        break;
      }
    }
  }

  draw() {
    const q = [];

    q.push([this.root, null, 0]);

    while (q.length > 0) {
      const [node, parent, level] = q.shift();
      node.setParent(parent);
      node.setLevel(level);
      this.level = Math.max(level, this.level);
      const [v, l, r] = this.nodes[node.value];

      if (l != -2) {
        node.setLeft(this.pointer[l]);
        q.push([this.pointer[l], node, level + 1]);
      }

      if (r != -2) {
        node.setRight(this.pointer[r]);
        q.push([this.pointer[r], node, level + 1]);
      }
    }

    this.result = Array.from(Array(this.level + 1), () => [Infinity, 0]);
  }

  findLeftMost(node) {
    let leftMost = node;
    while (leftMost.left != null) {
      leftMost = leftMost.left;
    }
    return leftMost;
  }

  // findLocation() {
  //   const q = [];
  //   const leftMost = this.findLeftMost(this.root);
  //   leftMost.setLocation(this.location++);

  //   q.push(leftMost);
  //   console.log(this.parents);
  //   while (this.location <= N) {
  //     let now = q.shift();
  //     console.log(now.value);

  //     if (now.location != null) {
  //       if (now.parent != null) q.push(now.parent);
  //     } else if (now.right == null) {
  //       now.parent.setLocation(this.location++);
  //       q.push(now.parent);
  //     } else {
  //       const newLeft = this.findLeftMost(now.right);
  //       newLeft.setLocation(this.location++);
  //       q.push(newLeft);
  //     }
  //   }
  // }

  inorder(node) {
    if (node) {
      this.inorder(node.left);
      node.location = this.location++;
      this.inorder(node.right);
    }
  }

  findResult(node) {
    // console.log(node.value + 1, node.level + 1, node.location);
    const [min, max] = this.result[node.level];
    this.result[node.level] = [
      Math.min(node.location, min),
      Math.max(node.location, max),
    ];

    if (node.left != null) {
      this.findResult(node.left);
    }

    if (node.right != null) {
      this.findResult(node.right);
    }
  }

  printAnswer() {
    let answer = [0, 0];

    this.result.forEach((v, i) => {
      const level = i + 1;
      const [min, max] = v;
      const length = max - min + 1;
      if (answer[1] < length) {
        answer[0] = level;
        answer[1] = length;
      }
    });

    console.log(answer.join(" "));
  }
}

const fs = require("fs");
const input = fs
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [N] = input.shift();

const nodes = input.map((v) => v.map((x) => x - 1)).sort((a, b) => a[0] - b[0]);

const t = new Tree(nodes);

t.createNode();

t.findRoot();

t.draw();

t.inorder(t.root);

t.findResult(t.root);

t.printAnswer();