二叉树的最大宽度

2021-04-07

题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例
示例 1:
输入:

     1
   /   \
  3     2
 / \     \  
5   3     9

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

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

注意: 答案在32位有符号整数的表示范围内。

解题思路：

          1(0)
        /   \
(2 * 0)3     2(2 * 0 + 1 = 1)
      / \     \  
(2*0)5   3     9 (2*1+1=3)
       (2*0+1=1)

由上图可知左孩子是它的父节点的编号的2倍，即2i,右孩子是它的父节点的2i+1,那么每一层的宽度就为:
第一层：0 - 0 + 1 = 1宽度为1
第二层：1 - 0 + 1 = 2宽度为2
第三层：3 - 0 + 1 = 4宽度为4
…
即每一层的宽度就为该层最右边节点的编号 - 最左边节点的编号 + 1

但是这样就会有个小问题：即编号逐渐增大，超出范围怎么办：如果每一层都可以减去一个固定的值那么结果即不会变，而且数也不会超出这个范围，而且这个数不能为负数。
所以我们可以取该节点的父节点那一层中最小的数。(该数肯定不为负数，且该数肯定比当前层的数要小于或者等于)

/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function(root) {
    //判断边界条件
    if  (!root) return 0;
    //设置max用于输出最大宽度
    let max = 1;
    //定义一个二维数组，用于存储当前层的节点编号和节点本身[[编号，节点],[编号，节点]]
    //初始化二维数组，里面存储的是根节点和它的编号0
    let que = [[0, root]];
    //当二维数组不为空时，循环运行
    while (que.length) {
        //获取当前层的宽度并和max比较=》取较大值
        //当前层的宽度为二维数组最后一个元素的编号-第一个元素的编号 + 1
        let width = que[que.length - 1][0] - que[0][0] + 1;
        //比较max和width
        if (width > max) max = width;
        //设置一个min,用于获取当前层的最小值，下面的编号需要减去这个最小值，以防止超出范围
        //当前层最小值是第一个元素的编号
        let min = que[0][0];
        //获取下一层的数据，并替换当前二维数组
        let temp = [];
        //获取数组并解构[编号，节点]
        for (let [ind, node] of que) {
            //如果当前节点有左孩子，就放入数组中
            node.left && temp.push([(ind - min) * 2, node.left]);
            //如果当前节点有右孩子，就放入数组中
            node.right && temp.push([(ind - min) * 2 + 1, node.right]);
        }
        //此时temp就为下一层的数据->temp替换que中的数据，进行下一轮循环
        que = temp;
    }
    return max;
}