662. 二叉树最大宽度

题目描述

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

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

提示：

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

解题思路

　　使用广度优先搜索方法，求出每一层的宽度，从而比较出最大宽度。根据题目意思，并不是简单得求取一层中所有非空节点的个数作为宽度，因此考虑使用二叉树节点编号来标记最左和最右非空节点，那么宽度为（right-left+1）。

　　二叉树节点编号方式：根节点编号为1，设当前节点编号为index，那么其左节点编号为index*2，右节点编号为inde*2+1。如下图所示：

　　注意，当二叉树中链式结构（多个层中只有一个节点）居多时，会导致节点编号溢出（比如，由3000个节点组成的链式结构，最后一个节点的编号为2³⁰⁰⁰）。因此，这里我使用重置编号的方式来解决这个溢出问题。每当遇到节点数为1的层，就重新将该层的唯一节点编号为1，因为该节点也是往下遍历的其他层的节点的根节点。

代码如下

/**
 * 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) {
    const list = [];
    let max = 0;
    list.push([root,1]); //以[节点，节点编号]的形式存储节点
    let len = list.length;

    //参考二叉树层次遍历
    while(len>0){
        let left = -1;
        let right = -1;
        for(let i=0;i<len;i++){
            let cur = list.shift();

            if(len===1){//当该层节点数只有1个时，重置节点编号，把该节点编号置1
                cur[1] = 1;
            }else{
                if(i===0){
                    left = cur[1];
                }
                if(i===len-1){
                    right = cur[1];
                }
            }
            
            //存储左右子节点
            if(cur[0].left){
                let index= cur[1]*2;
                list.push([cur[0].left,index]);
            }
            if(cur[0].right){
                let index = cur[1]*2+1;
                list.push([cur[0].right,index]);
            }
        }
        max = Math.max(max,right-left+1);
        len = list.length;
    }
    return max;
};