662. Maximum Width of Binary Tre

二叉树的宽度

层序遍历，超时了。

/**
 * 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) {
  if (!root) return 0;
  let max = 0;
  const queue = [root];
  
  while(queue.length) {
    let n = queue.length;
    max = Math.max(max, n); 
    
    for(let i = 0; i < n; i++) {
      const node = queue.shift();
      queue.push(node ? node.left : null);
      queue.push(node ? node.right : null);
    }
    while(queue.length && !queue[queue.length - 1]) queue.pop();
    while(queue.length && !queue[0]) queue.shift();
    
  }
  return max;
};

由于题目约束，答案在32位有符号整数的表示范围内。js用这些方法的时候会越界，可以采用办法剪枝，保证pos不越界。

剪枝方法：当当前层数只有一层的时候，pos重置到0

var widthOfBinaryTree = function(root) {
  if (!root) return 0;
  const queue = [[root, 0]];
  let width = 0;
  while (queue.length) {
    const len = queue.length;
    if (len === 1) {
      queue[0][1] = 0;
    }
    let left = Infinity;
    let right = -Infinity;
    for (let i = 0; i < len; i++) {
      const [node, index] = queue.shift();
      left = Math.min(index, left);
      right = Math.max(index, right);
      
      if (node.left) {
        queue.push([node.left, 2 * index]);
      }
      if (node.right) {
        queue.push([node.right, 2 * index + 1]);
      }
    }
    width = Math.max(width, right - left + 1);
  }
  return width;
};

• Runtime: 142 ms, faster than 12.26%
• Memory Usage: 43.1 MB, less than 94.19%

/**
 * 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) {
  if (!root) return 0;
  const queue = [[root, 0]];
  let width = 0;
  while (queue.length) {
    const len = queue.length;
    if (len === 1) {
      queue[0][1] = 0;
    }
    let left = Infinity;
    let right = -Infinity;
    for (let i = 0; i < len; i++) {
      const [node, index] = queue.shift();
      left = Math.min(index, left);
      right = Math.max(index, right);
      
      if (node.left) {
        queue.push([node.left, 2 * index]);
      }
      if (node.right) {
        queue.push([node.right, 2 * index + 1]);
      }
    }
    width = Math.max(width, right - left + 1);
  }
  return width;
};