层序变种

层序骨架中哪些部分是固定的？

• 固定: 队列 + 每轮先取 size, 循环 size 次处理一层, 见 层序遍历;
• 变化: 只改 "每层如何收集结果", 下面的题目都是同一骨架的变体;

锯齿形层序遍历怎么做？

• 要求: 奇数层从左到右, 偶数层从右到左;
• 实现: 维护布尔量 odd, 偶数层用 unshift 反向插入, 每层结束取反;

const zigzagLevelOrder = function (root) {
  if (root == null) return [];
  const res = [];
  const queue = [root];
  let odd = true;
  while (queue.length > 0) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      odd ? level.push(node.val) : level.unshift(node.val);
      if (node.left != null) queue.push(node.left);
      if (node.right != null) queue.push(node.right);
    }
    res.push(level);
    odd = !odd;
  }
  return res;
};

右视图如何取？

• 要求: 返回每层最右侧节点的值;
• 实现: 每层出队前读队尾元素; 也可以整层收集后取最后一个;

const rightSideView = function (root) {
  if (root == null) return [];
  const res = [];
  const queue = [root];
  while (queue.length !== 0) {
    res.push(queue[queue.length - 1].val);
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left != null) queue.push(node.left);
      if (node.right != null) queue.push(node.right);
    }
  }
  return res;
};

最大宽度如何计算？

• 定义: 每层最左与最右非空节点之间的位置数, 中间的 null 也计入宽度;
• 索引规则: 根索引 0, 左子 2i + 1, 右子 2i + 2; 宽度 = 队尾索引 - 队首索引 + 1;
• 易错: 层数较多时索引会超出 Number 精度, 需要用 BigInt;

const widthOfBinaryTree = function (root) {
  const queue = [[root, 0n]];
  let res = 0n;
  while (queue.length !== 0) {
    const size = queue.length;
    const width = queue[size - 1][1] - queue[0][1] + 1n;
    if (width > res) res = width;
    for (let i = 0; i < size; i++) {
      const [node, index] = queue.shift();
      if (node.left != null) queue.push([node.left, 2n * index + 1n]);
      if (node.right != null) queue.push([node.right, 2n * index + 2n]);
    }
  }
  return res;
};

如何检验完全二叉树？

• 判据: 层序第一次遇到空节点之后, 不能再出现非空节点;
• 实现差异: 空节点也要入队, 并用标记记录是否已经出现过空节点;

const isCompleteTree = function (root) {
  if (root == null) return true;
  const queue = [root];
  let seenNull = false;
  while (queue.length !== 0) {
    const node = queue.shift();
    if (node == null) {
      seenNull = true;
      continue;
    }
    if (seenNull) return false;
    queue.push(node.left);
    queue.push(node.right);
  }
  return true;
};

• 复杂度: 以上各题均为时间 O(n), 空间 O(n);