给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

    每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

    示例 1:

    输入: 

    1.        1<br />         /   \<br />        3     2<br />       / \     \  <br />      5   3     9

    输出: 4
    解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
    示例 2:

    输入: 

          1<br />         /  <br />        3    <br />       / \       <br />      5   3

    输出: 2
    解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
    示例 3:

    输入: 

          1<br />         / \<br />        3   2 <br />       /        <br />      5

    输出: 2
    解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
    示例 4:

    输入: 

          1<br />         / \<br />        3   2<br />       /     \  <br />      5       9 <br />     /         \<br />    6           7<br />输出: 8<br />解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

    /**
 * 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 maxWidth = 0; // 全局维护最大值

    let left = 0; // 记录当前层最左边节点的计数值
    let right = 0; // 记录当前层最右边节点的计数值

    while (queue.length) {
        left = queue[0][1];
        const len = queue.length;
        for (let i = 0; i < len; i += 1) {
            let [node, depth] = queue.shift();
            right = depth;
            if (node.left) {
                queue.push([node.left, 2 * (depth - left)])
            }; // 重点，优化掉左边不需要计数的部分
            if (node.right) {
                queue.push([node.right, 2 * (depth - left) + 1])
            };
        }
        maxWidth = Math.max(maxWidth, right - left + 1);
    }
    return maxWidth
};

    image.png