662. 二叉树最大宽度

发表于 | 分类于
宽度优先遍历

用时：120min

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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出栈同步，用于计算左右距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
};

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

然后翻了翻答案

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
};