数据结构与算法之LeetCode-662. 二叉树最大宽度 -（DFS，BFS）

662. 二叉树最大宽度 - 力扣（LeetCode）

• 根节点的位置为1（index
• 左子节点的位置就为1*2
• 右子节点的位置就为1*2+1
  • 节点下标会非常大（2**3000）个子节点，超过JS的number范围，因此需要使用bigint避免溢出

var widthOfBinaryTree = function(root) {
   // bfs
  const queue = [[root,1n]];
  let max = -1;
  while(queue.length){
    const size = queue.length;
    max = Math.max(max,Number(queue[queue.length-1][1]-queue[0][1]+1n));
    for(let i=0;i<size;i++){
      const [node,index] = queue.shift();
      if(node.left){
         queue.push([node.left,index*2n])
      }
      if(node.right){
        queue.push([node.right,index*2n+1n])
      }
      
    }
  }
  return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

执行结果：通过

执行用时：60 ms, 在所有 JavaScript 提交中击败了98.72%的用户

内存消耗：47.1 MB, 在所有 JavaScript 提交中击败了31.91%的用户

通过测试用例：114 / 114

function widthOfBinaryTree(root: TreeNode | null): number {
    const queue: [TreeNode, bigint][] = [[root, 1n]]
    let max = -1
    while (queue.length) {
        const size = queue.length
        max = Math.max(max, Number(queue[queue.length - 1][1] - queue[0][1] + 1n))
        for (let i = 0; i < size; i++) {
            const [node, index] = queue.shift()
            node?.left && queue.push([node.left, index * 2n])
            node?.right && queue.push([node.right, index * 2n + 1n])
        }
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

var widthOfBinaryTree = function(root) {
    /** JS 存在计数溢出的问题，使用 BigInt，BigInt 不能调用 Math 中的方法。 */
    let maxWidth = 1n;
    const leftIds = []
    const dfs = (root, level, currIdx) => {
        if (leftIds[level] === undefined) {
            leftIds[level] = currIdx;
        } else {
            const width = currIdx - leftIds[level] + 1n;
            maxWidth = maxWidth > width ? maxWidth : width;
        }
        if (root.left !== null) {
            dfs(root.left, level + 1, currIdx * 2n - 1n);
        }
        if (root.right !== null) {
            dfs(root.right, level + 1, currIdx * 2n);
        }
    }
    dfs(root, 0, 1n);
    return maxWidth;    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

执行结果：通过

执行用时：80 ms, 在所有 JavaScript 提交中击败了32.55%的用户

内存消耗：45.9 MB, 在所有 JavaScript 提交中击败了55.89%的用户

通过测试用例：114 / 114

参考链接

662. 二叉树最大宽度 - 力扣（LeetCode）

二叉树最大宽度 - 二叉树最大宽度 - 力扣（LeetCode）

【wendraw】BFS 的简单应用 - 二叉树最大宽度 - 力扣（LeetCode）

[662. 二叉树最大宽度 - 二叉树最大宽度 - 力扣（LeetCode）](