用时：120min

一开始的思路是用BFS，出队时出一整队（后来知道这叫宽度遍历）

然后双指针找到左右节点。当左右节点都不存在时结束

var widthOfBinaryTree = function(root) {
    var que = [root]
    var max = 0    while(que.length) {
        var len = que.length        var left = 0        var right = que.length - 1        while(!que[left] && left < len) {
            left ++        }
        while(!que[right] && right >= 0) {
            right --        }
        if (left > right) {
            break        }
        max = Math.max(max,right - left+ 1)
        for(let i = 0 ; i < len ; i ++) {
            var node = que.shift()
            if (!node) {
                que.push(node)
                que.push(node)
                continue            }
            node.left ? que.push(node.left) : que.push(null)
            node.right ? que.push(node.right) : que.push(null)
        }
    }
    return max
};

很快啊，提交显示执行超过时间限制，于是增加了一个储存序号的队列，和BFS出栈同步，用于计算左右距离

var widthOfBinaryTree = function(root) {
    var que = [root]
    var numQue = [1]
    var max = 0    while(que.length) {
        var len = que.length        max = Math.max(numQue[numQue.length - 1] - numQue[0] + 1)
        for(let i = 0 ; i < len ; i ++) {
            var node = que.shift()
            var val = numQue.shift()
            if (node.left) {
                que.push(node.left)
                numQue.push(val * 2)
            }
            if (node.right) {
                que.push(node.right)
                numQue.push(val * 2 + 1)
            }
        }
    }
    return max
};

很快啊，告诉我栈溢出了。我这才意识到问题的严重性（误

然后翻了翻答案

对每次的下表统一减去了当层的第一个数

var widthOfBinaryTree = function(root) {
    var que = [root]
    var numQue = [0]
    var max = 0    while(que.length) {
        var len = que.length        var start = numQue[0]
        max = Math.max( numQue[numQue.length - 1]  - start  + 1,max)
        for(let i = 0 ; i < len ; i ++) {
            var node = que.shift()
            var val = numQue.shift() - start
            if (node.left) {
                que.push(node.left)
                numQue.push(val * 2 + 1 )
            }
            if (node.right) {
                que.push(node.right)
                numQue.push(val * 2 + 2 )
            }
        }
    }
    return max
};