广度优先搜索，深度优先搜索（前序遍历、中序遍历、后序遍历），递归、迭代（单栈、双栈和莫里斯），用减去每行起始序号技巧缩小数据范围，求解《662. 二叉树最大宽度》

var widthOfBinaryTree = function(root) { // 减去每行起始序号
  const q = [[root, 0]]
  let r = 0
  while (q.length) {
    let l = q.length
    const start = q[0][1]
    while (l--) {
      const [n, w] = q.shift()
      if (r < w - start + 1) r = w - start + 1
      if (n.left) q.push([n.left, (w - start) << 1])
      if (n.right) q.push([n.right, ((w - start) << 1) + 1])
    }
  }
  return r
};

var widthOfBinaryTree = function(root) { // BigInt
  const q = [[root, 0n]]
  let r = 0n
  while (q.length) {
    let l = q.length
    const start = q[0][1]
    while (l--) {
      const [n, w] = q.shift()
      if (r < w - start + 1n) r = w - start + 1n
      if (n.left) q.push([n.left, w * 2n])
      if (n.right) q.push([n.right, w * 2n + 1n])
    }
  }
  return r
};

function widthOfBinaryTree(root: TreeNode | null): number { // 指针实现广度优先搜索
  const q: [TreeNode, number][] = [[root, 0]]
  let start = 0, end = 1, r = 0
  while (start < end) {
    const l = end, first = q[start][1]
    while (start < l) {
      const [n, m] = q[start++]
      r = Math.max(r, m - first + 1)
      if (n.left) q[end++] = [n.left, (m - first) * 2]
      if (n.right) q[end++] = [n.right, (m - first) * 2 + 1]
    }
  }
  return r
};

class Solution {
  function widthOfBinaryTree($root) {
    $q = [[$root, 0]];
    $r = 1;
    while (count($q)) {
      $l = count($q);
      $first = $q[0][1];
      while ($l--) {
        list($n, $m) = array_shift($q);
        $r = max($r, $m - $first + 1);
        if ($n->left) $q []= [$n->left, ($m - $first) << 1];
        if ($n->right) $q []= [$n->right, (($m - $first) << 1) + 1];
      }
    }
    return $r;
  }
}

type pair struct {
  Node *TreeNode
  M int
}
func widthOfBinaryTree(root *TreeNode) int {
  q, r := []pair, 1
  for len(q) > 0 {
    l, first := len(q), q[0].M
    for l > 0 {
      n, m := q[0].Node, q[0].M
      q = q[1:]
      r = max(r, m - first + 1)
      if n.Left != nil {
        q = append(q, pair{n.Left, (m - first) << 1})
      }
      if n.Right != nil {
        q = append(q, pair{n.Right, ((m - first) << 1 + 1)})
      }
      l--
    }
  }
  return r
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

class Solution {
  public int widthOfBinaryTree(TreeNode root) {
    Deque<Pair<TreeNode, Integer>> q = new ArrayDeque<Pair<TreeNode, Integer>>();
    q.offerLast(new Pair<TreeNode, Integer>(root, 0));
    int r = 0;
    while (q.isEmpty() == false) {
      int l = q.size();
      int first = q.getFirst().getValue();
      while (l-- > 0) {
        Pair<TreeNode, Integer> p = q.pollFirst();
        TreeNode n = p.getKey();
        int m = p.getValue();
        r = Math.max(r, m - first + 1);
        if (n.left != null) q.offerLast(new Pair<TreeNode, Integer>(n.left, (m - first) << 1));
        if (n.right != null) q.offerLast(new Pair<TreeNode, Integer>(n.right, ((m - first) << 1) + 1));
      }
    }
    return r;
  }
}

public class Solution {
  public int WidthOfBinaryTree(TreeNode root) {
    Queue<Tuple<TreeNode, int>> q = new Queue<Tuple<TreeNode, int>>();
    q.Enqueue(new Tuple<TreeNode, int>(root, 0));
    int r = 1;
    while (q.Count > 0) {
      int l = q.Count, first = q.First().Item2;
      while (l-- > 0) {
        Tuple<TreeNode, int> t = q.Dequeue();
        TreeNode n = t.Item1;
        int m = t.Item2;
        r = Math.Max(r, m - first + 1);
        if (n.left != null) q.Enqueue(new Tuple<TreeNode, int>(n.left, (m - first) << 1));
        if (n.right != null) q.Enqueue(new Tuple<TreeNode, int>(n.right, ((m - first) << 1) + 1));
      }
    }
    return r;
  }
}

#define MAX(a, b) (a > b ? a : b)
typedef struct {
  struct TreeNode* n;
  long m;
} Pair;
int widthOfBinaryTree(struct TreeNode* root){
  Pair* q = malloc(sizeof(Pair) * 3000);
  int start = 0, end = 1, r = 1;
  q[start].n = root;
  q[start].m = 0;
  while (start < end) {
    int l = end;
    long first = q[start].m;
    while (start < l) {
      Pair p = q[start++];
      struct TreeNode* n = p.n;
      int m = p.m;
      r = MAX(r, m - first + 1);
      if (n->left) {
        q[end].n = n->left;
        q[end++].m = m - first << 1;
      }
      if (n->right) {
        q[end].n = n->right;
        q[end++].m = (m - first << 1) + 1;
      }
    }
  }
  return r;
}

class Solution {
public:
  int widthOfBinaryTree(TreeNode* root) { // emplace 实现：第一个参数为参数列表
    queue<pair<TreeNode*, int>> q;
    q.emplace(pair<TreeNode *, int>(root, 0));
    int r = 1;
    while (q.empty() == false) {
      int l = q.size(), first = q.front().second;
      while (l--) {
        pair<TreeNode*, int> p = q.front();
        q.pop();
        TreeNode* n = p.first;
        int m = p.second;
        r = max(r, m - first + 1);
        if (n->left) q.emplace(pair<TreeNode *, int>(n->left, m - first << 1));
        if (n->right) q.emplace(pair<TreeNode *, int>(n->right, (m - first << 1) + 1));
      }
    }
    return r;
  }
};

typedef pair<TreeNode*, int> p;
class Solution {
public:
  int widthOfBinaryTree(TreeNode* root) { // push 实现：第一个参数为参数
    queue<p> q;
    q.push({root, 0});
    int r = 1;
    while (q.empty() == false) {
      int l = q.size(), first = q.front().second;
      while (l--) {
        pair<TreeNode*, int> p = q.front();
        q.pop();
        TreeNode* n = p.first;
        int m = p.second;
        r = max(r, m - first + 1);
        if (n->left) q.push({n->left, m - first << 1});
        if (n->right) q.push({n->right, (m - first << 1) + 1});
      }
    }
    return r;
  }
};

class Solution:
  def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int: # list 实现
    q, r = [[root, 0]], 1
    while len(q):
      l, first = len(q), q[0][1]
      for _ in range(l, 0, -1):
        n, m = q.pop(0)
        r = max(r, m - first + 1)
        if n.left: q.append([n.left, m - first << 1])
        if n.right: q.append([n.right, (m - first << 1) + 1])
    return r

class Solution:
  def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int: # deque 实现
    q, r = deque([[root, 0]]), 1
    while len(q):
      l, first = len(q), q[0][1]
      for _ in range(l, 0, -1):
        n, m = q.popleft()
        r = max(r, m - first + 1)
        if n.left: q.append([n.left, m - first << 1])
        if n.right: q.append([n.right, (m - first << 1) + 1])
    return r

var widthOfBinaryTree = function(root) { // 减去每行起始序号
  const h = new Map
  let r = 1
  const d = (n, depth, m) => {
    if (n === null) return depth
    if (h.has(depth) === false) h.set(depth, m)
    else if (r < m - h.get(depth) + 1) r = m - h.get(depth) + 1
    d(n.left, depth + 1, (m - h.get(depth)) * 2)
    d(n.right, depth + 1, (m - h.get(depth)) * 2 + 1)
  }
  return d(root, 0, 0), r
};

var widthOfBinaryTree = function(root) { // BigInt
  const h = new Map
  let r = 1n
  const d = (n, depth, m) => {
    if (n === null) return depth
    if (h.has(depth) === false) h.set(depth, m)
    else if (r < m - h.get(depth) + 1n) r = m - h.get(depth) + 1n
    d(n.left, depth + 1, m * 2n)
    d(n.right, depth + 1, m * 2n + 1n)
  }
  return d(root, 0, 0n), r
};

#define MAX(a, b) (a > b ? a : b)
typedef struct {
  int key;
  long val;
  UT_hash_handle hh;
} HashItem;
void d(struct TreeNode* n, int depth, long m, HashItem* firsts, int* r) {
  if (n == NULL) return;
  HashItem* pEntry = NULL;
  HASH_FIND_INT(firsts, &depth, pEntry);
  if (pEntry == NULL) {
    pEntry = malloc(sizeof(HashItem));
    pEntry->key = depth;
    pEntry->val = m;
    HASH_ADD_INT(firsts, key, pEntry);
  }
  *r = MAX(*r, m - pEntry->val + 1);
  d(n->left, depth + 1, m - pEntry->val << 1, firsts, r);
  d(n->right, depth + 1, (m - pEntry->val << 1) + 1, firsts, r); 
}
int widthOfBinaryTree(struct TreeNode* root){
  HashItem* firsts = NULL;
  HashItem* pEntry = malloc(sizeof(HashItem));
  pEntry->key = 0;
  pEntry->val = 0;
  HASH_ADD_INT(firsts, key, pEntry);
  int r = 0;
  d(root, 0, 0, firsts, &r);
  return r;
}

var widthOfBinaryTree = function(root) {
  const h = new Map
  let r = 1
  const d = (n, depth, m) => {
    if (n === null) return depth
    if (h.has(depth) === false) h.set(depth, m)
    d(n.left, depth + 1, (m - h.get(depth)) * 2)
    if (r < m - h.get(depth) + 1) r = m - h.get(depth) + 1
    d(n.right, depth + 1, (m - h.get(depth)) * 2 + 1)
  }
  return d(root, 0, 0), r
};

class Solution:
  def d(self, n: Optional[TreeNode], depth: int, m: int):
    if n == None: return
    if depth not in self.firsts: self.firsts[depth] = m
    self.d(n.left, depth + 1, m - self.firsts[depth] << 1)
    self.r = max(self.r, m - self.firsts[depth] + 1)
    self.d(n.right, depth + 1, (m - self.firsts[depth] << 1) + 1)
  def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    self.firsts, self.r = dict(), 1
    self.d(root, 0, 0)
    return self.r

class Solution {
  private $firsts = [];
  function widthOfBinaryTree($root) {
    $stack = [];
    $p = $root;
    $r = 1;
    $p->depth = 0;
    $p->m = 0;
    $this->firsts[0] = 0;
    while (count($stack) || $p) {
      while ($p) {
        $stack []= $p;
        $r = $this->update($p->left, $p, 0, $r);
        $p = $p->left;
      }
      $n = array_pop($stack);
      $r = $this->update($n->right, $n, 1, $r);
      $p = $n->right;
    }
    return $r;
  }
  function update($cur, $prev, $right, $r) {
    $firsts = &$this->firsts;
    if ($cur !== null && $cur->depth === null) {
      $depth = $prev->depth;
      $m = $prev->m;
      $cur->depth = $depth + 1;
      $cur->m = ($m - $firsts[$depth] << 1) + $right;
      if ($firsts[$depth + 1] === null) $firsts[$depth + 1] = $cur->m;
      $r = max($r, $cur->m - $firsts[$depth + 1] + 1);
    }
    return $r;
  }
}

function widthOfBinaryTree(root: TreeNode | null): number {
  const stack: TreeNode[] = [], depths = new Map, ms = new Map, firsts = new Map
  let p = root, r = 1
  depths.set(p, 0)
  ms.set(p, 0)
  firsts.set(0, 0)
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      r = update(p.left, p, r, 0, depths, ms, firsts)
      p = p.left
    }
    const n = stack.pop()
     r = update(n.right, n, r, 1, depths, ms, firsts)
    p = n.right
  }
  return r
};
const update = (cur: TreeNode | null, prev: TreeNode, r: number, right: number, depths: Map<TreeNode, number>, ms: Map<TreeNode, number>, firsts: Map<number, number>) => {
  if (cur !== null && depths.has(cur) === false) {
    const depth = depths.get(prev), m = ms.get(prev)
    depths.set(cur, depth + 1)
    ms.set(cur, ((m - firsts.get(depth)) << 1) + right)
    if (firsts.has(depth + 1) === false) firsts.set(depth + 1, ms.get(cur))
    r = Math.max(r, ms.get(cur) - firsts.get(depth + 1) + 1)
  } 
  return r
}

var widthOfBinaryTree = function(root) {
  const h = new Map
  let r = 1
  const d = (n, depth, m) => {
    if (n === null) return depth
    if (h.has(depth) === false) h.set(depth, m)
    d(n.left, depth + 1, (m - h.get(depth)) * 2)
    d(n.right, depth + 1, (m - h.get(depth)) * 2 + 1)
    if (r < m - h.get(depth) + 1) r = m - h.get(depth) + 1
  }
  return d(root, 0, 0), r
};

func widthOfBinaryTree(root *TreeNode) int {
  r, firsts := 0, map[int]int{}
  var d func(n *TreeNode, depth int, m int)
  d = func(n * TreeNode, depth int, m int) {
    if n == nil {
      return
    }
    if _, ok := firsts[depth]; ok == false {
      firsts[depth] = m
    }
    if n.Left != nil {
      d(n.Left,  depth + 1, (m - firsts[depth]) << 1)
    }
    if n.Right != nil {
      d(n.Right, depth + 1, (m - firsts[depth]) << 1 + 1)
    }
    r = max(r, m - firsts[depth] + 1)
  }
  d(root, 0, 0)
  return r
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}