统计二叉树每一层的宽度
哪些公司问过
答案要点
- 宽度含中间空位置,需按完全二叉树编号:根为 1,左孩子 2i,右孩子 2i+1
- BFS 层序遍历,按层记录第一个和最后一个节点编号
- 每层宽度 = 最后编号 - 第一个编号 + 1
- 每层编号减去该层首个编号,使用相对编号防止溢出
- 时间 O(n),空间为队列大小
易错点
- 只统计每层非空节点数,忽略中间空位置
- 编号直接用 int 累乘,深树下溢出
- 在一层内混入下一层节点,导致首尾编号取错
面试官常见追问
- 用 DFS 怎么做?
- 如果只求最大宽度呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场