网络异常，图片无法展示
|
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree） 结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。 复制代码
示例 2:
输入: 1 / 3 / \ 5 3 输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。 复制代码
示例 3:
输入: 1 / \ 3 2 / 5 输出: 2 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。 复制代码
示例 4:
输入: 1 / \ 3 2 / \ 5 9 / \ 6 7 输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。 复制代码
注意: 答案在32位有符号整数的表示范围内。
因为每一层的宽度被定义为两个端点之间的长度，所以想要获取每一层的宽度，首先需要获取这两个端点，也就是获取每一层的真实节点
获取到端点之后，如何获取它们之间的长度呢？
我们可以给每一个节点一个下标，这样两个端点的下标值相减，就是它们之间的宽度。
如果给每个节点定义下标呢？
这里通过如下规则定义：
左子节点的下标为父节点下标 ind*2-1
右子节点的下标为父节点下标 ind*2
有了每层的端点节点以及它们的下标，就可以获取每一层的宽度，然后对比每一层的宽度，获取最大值，就是整棵二叉树的最大宽度。
动画演示如下：
网络异常，图片无法展示
|
代码如下：
var widthOfBinaryTree = function(root) { // 每层节点的下标数组，取模运算的值 const arr = [],mod = 10000000007; // 获取每一层节点的下标 function getNodeInd(root,deep,ind){ if(root === null) return; if(!arr[deep]) arr[deep] = []; arr[deep].push(ind); getNodeInd(root.left,deep+1,(ind*2-1)%mod); getNodeInd(root.right,deep+1,(ind*2)%mod); }; getNodeInd(root,0,1); // 初始化最大宽度为1 let max = 1; // 遍历下标数组 for(let i = 1;i<arr.length;i++){ // 如果当前层节点数量大于1，计算宽度 if(arr[i].length>1){ max = Math.max(max,arr[i].pop()-arr[i][0]+1) } } // 返回结果值 return max; }; 复制代码
至此我们就完成了 leetcode-662-二叉树最大宽度
如有任何问题或建议，欢迎留言讨论！
