题目名称

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例

输入：root = [1,3,2,5,3,null,9]

输出：4

解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

题解

这道题主要是要注意中间包含空节点

广度优先遍历

使用广度优先遍历方法，将数根据层级分成二维数组，中间的空节点用 null 填充，最后比较 数组左右两侧第一个不为空的元素位置之差

但是这个方法由于数组存储元素过多，会造成内存溢出

广度优先遍历 + 序号

这个依旧是是使用广度优先遍历方法，但是空节点不在填充，而通过序号来重新记录节点在当前层级的序号

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var widthOfBinaryTree = function(root) {
    if(!root.left && !root.right) return 1
    return flatRoot([[root, 1n]])
};


var flatRoot = (arr, max = 0n) => {
    let newArr = []
    if(max < arr[arr.length - 1][1] - arr[0][1] + 1n) {
        max = arr[arr.length - 1][1] - arr[0][1] + 1n
    }
    for(let i = 0; i < arr.length; i++) {
        let item = arr[i]
        item[0].left && newArr.push([item[0].left, item[1] * 2n]) 
        item[0].right && newArr.push([item[0].right, item[1] * 2n + 1n]) 
    }
    if(newArr.length === 0) return max
    return flatRoot(newArr, max)
}