Lstmxx的空间

662. 二叉树最大宽度

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

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

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

type Que = {
  depth: number;
  pos: bigint;
  node: TreeNode | null;
}

function widthOfBinaryTree(root: TreeNode | null): bigint {
  let ans = 0n
  if (root === null) return ans
  const nodeQues: Que[] = [{
    depth: 0,
    pos: 0n,
    node: root
  }]
  let curDepth = 0
  let left = 0n
  while(nodeQues.length) {
    const { depth, pos, node } = nodeQues.shift()
    if (node) {
      nodeQues.push({ node: node.left, depth: depth + 1, pos: pos * 2n })
      nodeQues.push({ node: node.right, depth: depth + 1, pos: pos * 2n + 1n })
      if (curDepth !== depth) {
        curDepth = depth
        left = pos
      }
      let res = pos - left + 1n
      ans = res > ans ? res : ans
    }
  }
  return ans
};