/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function (root) {
  // root 는 배열이 아닌 node 이다.

  if (root.left === null && root.right === null) return 1;
  // root.left 와 root.right 이 null 일 경우 너비는 1

  const queue1 = [root];
  const queue2 = [];
  let shiftingQueue = queue1;
  let pushingQueue = queue2;
  // queue 2 개를 선언해서 역할을 번갈아 바꿔주며 사용했다.
  // shiftingQueue : 저장된 node 들을 shift 하는 queue
  // pushingQueue : shiftingQueue 에서 꺼낸 node 의 자식 node 들을 저장해주는 곳이다.

  let currentNode;
  let maxWidth = 1;

  while (true) {
    currentNode = shiftingQueue.shift();

    if (currentNode === null) currentNode = new TreeNode(null);
    // getWidth 함수에서 현재 level 의 너비를 구하려면 null 도 모두 포함된 node 의 배열이 필요하다고 판단했다.
    // 그래서 currentNode 가 null 이어도 자식 node (null) 를 갖도록 TreeNode 인스턴스를 만들어 넣어주었다. (TreeNode 는 최 상단 jsDoc 에 정의됨)

    pushingQueue.push(currentNode.left);
    pushingQueue.push(currentNode.right);
    // 좌우 자식 노드를 저장

    if (shiftingQueue.length === 0) {
      const width = getWidth(pushingQueue);
      // 저장된 queue 로 현재 level 의 너비를 구함

      if (width === 0) break;
      // 만약 현재 level 의 배열이 null 로만 이루어져 있으면 0 으로 return 된다.
      // 즉 더 이상 하위 level 이 없으므로 while loop 을 중단

      maxWidth = Math.max(width, maxWidth);
      shiftingQueue = shiftingQueue === queue1 ? queue2 : queue1;
      pushingQueue = pushingQueue === queue1 ? queue2 : queue1;
      // Queue 의 역할 swap
    }
  }

  // 층별 너비 구하는 함수 (양 끝 포인터를 좁혀가며 end point 찾음)
  function getWidth(array) {
    let left = 0;
    let right = array.length - 1;

    while (array[left] === null || array[right] === null) {
      // 해당 자리의 요소가 null 이면 pointer 를 옮긴다.
      if (array[left] === null) left++;
      if (array[right] === null) right--;
      if (left > right) return 0;
      // 만약 left pointer 가 더 커졌다는 말은
      // null 로만 이뤄져 있다는 말이므로 return 0 (너비 0)
    }
    return right - left + 1; // 너비 구함 (inclusive)
  }
  return maxWidth;
};

const widthOfBinaryTree = (root) => {
  const queue = [{ node: root, pos: 0 }];
  // queue 를 하나만 사용했다.
  // node 를 재구성해 position(pos) 값을 표시해준다.

  let maxWidth = 0;

  while (queue.length) {
    const levelLength = queue.length;
    // 해당 level 의 길이 (node 의 수) = 현재 queue 의 길이와 동일하다.

    let min = Number.MAX_VALUE;
    let max = 0;

    for (let i = 0; i < levelLength; i++) {
      // level 의 길이만큼 내부 loop

      const curr = queue.pop();
      min = Math.min(min, curr.pos);
      max = Math.max(max, curr.pos);
      // position 값을 저장해두니 간단하게
      // 왼쪽 pointer (min) 오른쪽 pointer (max) 정할 수 있다.

      // 자식 node queue 에 추가
      // (빼낼 때 pop() 을 하므로 unshift 로 추가하는데
      //  반대로 추가를 push() 빼낼 때 shift() 가 더 효율적이지 않을까 싶다.
      //  shift 연산은 push 연산에 비해 비효율적이고
      //  자식 두개를 추가, 하나를 빼주므로 추가가 더 빈번하다.)
      if (curr.node.left)
        queue.unshift({ node: curr.node.left, pos: curr.pos * 2 + 1 });

      if (curr.node.right)
        queue.unshift({ node: curr.node.right, pos: curr.pos * 2 + 2 });
      // 가장 획기적인 부분은 자식 node 의 position 값을 (부모 pos * 2 + 1 / + 2) 을 해준부분이다.
      // 이렇게 해주면 내 풀이에서 고민했던 너비를 구하기 위해 null 을 배열에
      // 채워주는 과정이 불필요해진다.
      // position 값을 표시하고 position 값을 창의적으로 assign 하면서
      // 엄청난 효율성을 얻은 코드이다.
    }

    // level 의 길이가 1 일 땐 너비도 1이다.
    const levelWidth = levelLength === 1 ? 1 : max - min + 1;
    maxWidth = Math.max(maxWidth, levelWidth);
  }

  return maxWidth;
};