二叉树最大宽度(LeetCode 662)
哪些公司问过
答案要点
- 宽度含两端非空节点之间的空节点,需按满二叉树位置编号
- 编号规则:左孩子 2i,右孩子 2i+1,每层宽度为末编号减首编号加 1
- 防溢出:每层编号减去该层首编号再向下计算,光用无符号 64 位不够
- BFS 或 DFS(记录每层最左编号)均可,时间空间 O(n)
- 边界:空树返回 0;若题意是每层节点数最大值,统计各层队列长度即可
易错点
- 只数每层非空节点数,与题目宽度定义不符
- 编号不做归一化导致整数溢出
- 每层宽度忘记加 1
- 以为换成 64 位整数就不会溢出:深树的编号是 2 的深度次方
面试官常见追问
- 为什么编号会溢出?
- DFS 解法的空间复杂度是多少?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场