#662
中等
低频
深度优先遍历二叉树最大宽度
这是一道围绕树、二叉树展开的高频练习。建议先掌握「深度优先遍历」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
题目分析
这道题表面上是在处理「二叉树最大宽度」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 树、二叉树 这些能力。这类题更像在一棵决策树里向下展开，关键是递归时带什么状态、什么时候回退。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：DFS 递归时给每个节点编号，并记录每层最左编号，用当前编号减去最左编号计算层宽。
推荐代码
推荐解法：深度优先遍历
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： DFS 递归时给每个节点编号，并记录每层最左编号，用当前编号减去最左编号计算层宽。
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int ans;
public int widthOfBinaryTree(TreeNode root) {
dfs(root, 1, 0);
return ans;
}
void dfs(TreeNode root, int u, int depth) {
if (root == null) return ;
if (!map.containsKey(depth)) map.put(depth, u);
ans = Math.max(ans, u - map.get(depth) + 1);
u = u - map.get(depth) + 1;
dfs(root.left, u << 1, depth + 1);
dfs(root.right, u << 1 | 1, depth + 1);
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用带编号的 DFS，而不是只数每层节点个数。
核心过程
- 递归时给每个节点一个完全二叉树式的位置编号。
- 记录每一层第一次出现的最左编号。
- 当前节点到该层最左编号的差值，就能算出当前层宽度。
- 遍历过程中持续更新全局最大宽度。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)。
面试补一句：这题最重要的认识是：宽度取决于位置跨度，不只是节点数量。
核心思路
最大宽度的关键不只是统计节点个数，而是保留完全二叉树意义下的相对位置。给节点编号后，宽度就能转成同层编号差。
步骤讲解
1
递归时维护节点位置编号
根节点记为 1，左孩子是 2*i，右孩子是 2*i+1。
为什么这样做：编号能保留空洞位置，从而正确计算宽度。
对应代码提示：dfs(node.left, depth + 1, index * 2);
2
记录每层第一个节点编号
第一次到达某一层时，把该层最左编号记下来。
为什么这样做：后续同层宽度都以这个最左位置为基准。
对应代码提示：if (!leftmost.has(depth)) leftmost.set(depth, index);
3
用当前编号减去最左编号更新答案
同层宽度等于 index - leftmost + 1。
为什么这样做：编号差天然表达了这层最左和最右非空节点之间的跨度。
对应代码提示：answer = Math.max(answer, index - leftmost.get(depth) + 1);
易错点
只统计每层节点数
中间有空洞时，节点数不等于题目要求宽度。
正确理解：必须保留相对位置编号。
每层最左编号没固定
宽度基准会漂移，答案错误。
正确理解：只在第一次到达该层时记录最左编号。
编号溢出风险没考虑
深树上编号可能变大。
正确理解：可用 long 或在每层相对归一化。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比纯 BFS 数层节点更准确，因为能保留空缺位置。
适用判断：树题若答案和“相对位置”有关，优先考虑编号技巧。
额外提醒
- 完全二叉树式编号，是把结构宽度转成数字差的关键。
动画演示
如果你还没完全看懂，可以展开动画演示。
深度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
深度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树结构，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。