二叉树最大宽度

题目

题目来源：力扣（LeetCode

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入:

       1<br />         /   \<br />        3     2<br />       / \     \  <br />      5   3     9 

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

输入:

      1<br />         /  <br />        3    <br />       / \       <br />      5   3     

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

输入:

      1<br />         / \<br />        3   2 <br />       /        <br />      5      

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

输入:

      1<br />         / \<br />        3   2<br />       /     \  <br />      5       9 <br />     /         \<br />    6           7<br />输出: 8

解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。

思路分析：

要求树的最大宽度，我们就需要遍历树的每个节点，在遍历树的过程中，给每个节点一个 index 值，如果我们走向左子树，那么 index -> index 2；如果我们走向右子树，那么 index -> index 2 + 1 。当我们在看同一层深度的位置 L 和 R 的时候，宽度就是 R - L + 1 。

例如在上面的树中，给根节点设置 index 为 1 ，根据宽度优先搜索顺序遍历每个节点，那么根节点的左子节点 3 的index 为 2，即 root.left = root 的 index 2；根节点的右子节点 2 的index 为 3，即 root.right = root 的 index 2 + 1，其它深度的节点以此类推。对于每⼀个 深度，第⼀个遇到的节点是最左边的节点，最后⼀个到达的节点是最右边的节点。

const widthOfBinaryTree = function(root) {
    if (!root) return;
  let max = 1n;
  // 定义一个二维数组，存储当前层的序号和存入的节点
  let que = [ [0n, root] ];
  while(que.length) {
    // width = Rindex - Lindex + 1
      const width = que[que.length - 1][0] - que[0][0] + 1n;
    if (width > max) max = width;
    let temp = [];
    for (const [i, q] of que) {
        q.left && temp.push([i * 2n, q.left]);
      q.right && temp.push([i * 2n + 1n, q.right]);
    }
    que = temp;
  }
  return Number(max);
}