Leetcode 662: 二叉树最大宽度
Leetcode 662: 二叉树最大宽度 是一道考察树的层序遍历和位编号思想的经典题目。其目标是找到二叉树的每一层的最大宽度，宽度定义为：最左节点和最右节点间的节点数（包含这两个节点，中间可以有空节点）。
题目描述
- 给定一个二叉树的根节点
root，返回其最大宽度。 - “宽度”定义为：
- 每层最左节点（即层级中最左非空节点）到最右节点之间节点的数目。
- 如果同一层只有一个非空节点，则宽度为 1。
解法 1：层序遍历 + 队列 (广度优先搜索 BFS)
思路
- 维护位置信息：
- 使用广度优先遍历 BFS，同时为每个节点分配一个基于完全二叉树的编号。根节点的编号为
1，左孩子为2 * x，右孩子为2 * x + 1。 - 每层的宽度可通过计算该层最右节点和最左节点对应编号的差值
width = right - left + 1。
- 使用广度优先遍历 BFS，同时为每个节点分配一个基于完全二叉树的编号。根节点的编号为
- 层序遍历逐层更新最大宽度：
- 使用一个队列，存储每层节点和它们的编号
(node, index)； - 遍历每一层时，记录最左节点和最右节点对应的编号，然后计算宽度，更新最大值。
- 使用一个队列，存储每层节点和它们的编号
代码模板
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
// 队列存节点和它的"编号" (1-based index for position)
Deque<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
queue.offer(new Pair<>(root, 1));
int maxWidth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
int left = queue.peekFirst().getValue(); // 当前层最左的编号
int right = queue.peekLast().getValue(); // 当前层最右的编号
maxWidth = Math.max(maxWidth, right - left + 1);
for (int i = 0; i < size; i++) {
Pair<TreeNode, Integer> pair = queue.poll();
TreeNode node = pair.getKey();
int index = pair.getValue();
// 添加左右孩子到队列
if (node.left != null) {
queue.offer(new Pair<>(node.left, 2 * index));
}
if (node.right != null) {
queue.offer(new Pair<>(node.right, 2 * index + 1));
}
}
}
return maxWidth;
}
}
复杂度分析
- 时间复杂度：O(n)
- 每个节点入队和出队各一次，总的时间复杂度为 O(n)。
- 空间复杂度：O(n)
- 最差情况下，队列存储所有节点 (如完全二叉树的某一层)。
解法 2：DFS 深度优先搜索 + 位编号
思路
- 递归方法：
- 对每个节点，按照广度优先编号规则计算其位置索引，然后递归处理左、右子树。
- 使用一个
Map<Integer, Integer>记录每层的最左节点编号。 - 对每个节点，计算当前宽度：
width = currentIndex - leftIndexAtCurrentLevel + 1。 - 同时在递归过程中维护最大宽度值。
关键步骤
- 递归传递 当前节点的编号 和 层级信息。
- 递归更新宽度：
- 如果是当前层第一个访问的节点，记录它的编号为该层的最左编号。
- 更新当前层宽度，调整全局最大宽度。
- 对左右子树分别递归处理：
- 左子树位置编号为
2 * currentIndex； - 右子树位置编号为
2 * currentIndex + 1。
- 左子树位置编号为
代码模板
class Solution {
public int widthOfBinaryTree(TreeNode root) {
Map<Integer, Integer> leftMostPos = new HashMap<>(); // 每层最左节点的编号
return dfs(root, 0, 1, leftMostPos);
}
private int dfs(TreeNode node, int depth, int index, Map<Integer, Integer> leftMostPos) {
if (node == null) return 0;
// 如果当前层是第一次访问，记录最左位置
leftMostPos.computeIfAbsent(depth, x -> index);
// 当前宽度 = 当前节点的编号 - 当前层最左编号 + 1
int currentWidth = index - leftMostPos.get(depth) + 1;
// 递归求左右子树的最大宽度
int leftWidth = dfs(node.left, depth + 1, 2 * index, leftMostPos);
int rightWidth = dfs(node.right, depth + 1, 2 * index + 1, leftMostPos);
// 返回当前层和左右子树的最大宽度
return Math.max(currentWidth, Math.max(leftWidth, rightWidth));
}
}
复杂度分析
- 时间复杂度：O(n)
- 每个节点只访问一次。
- 空间复杂度：O(h)
- 递归调用栈的最大深度为树的高度，最差情况为 O(n)（如链状树）。
解法 3：BFS 优化（直接计算宽度）
优化点
相比解法 1 的队列实现，这里省略使用 Pair 来记录编号数，直接在每层中计算 start 和 end 的编号即可。
代码模板
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
Deque<TreeNode> nodeQueue = new ArrayDeque<>();
Deque<Integer> indexQueue = new ArrayDeque<>();
nodeQueue.offer(root);
indexQueue.offer(1);
int maxWidth = 0;
while (!nodeQueue.isEmpty()) {
int size = nodeQueue.size();
int startIndex = indexQueue.peekFirst();
int endIndex = indexQueue.peekLast();
maxWidth = Math.max(maxWidth, endIndex - startIndex + 1);
for (int i = 0; i < size; i++) {
TreeNode currNode = nodeQueue.poll();
int currIndex = indexQueue.poll();
if (currNode.left != null) {
nodeQueue.offer(currNode.left);
indexQueue.offer(2 * currIndex);
}
if (currNode.right != null) {
nodeQueue.offer(currNode.right);
indexQueue.offer(2 * currIndex + 1);
}
}
}
return maxWidth;
}
}
复杂度分析
- 时间复杂度：O(n)
- 每个节点入队、出队各一次。
- 空间复杂度：O(n)
- 队列需要存储某一层的所有节点。
快速AC策略
- 选择解法：
- 如果面试中强调代码可读性：写BFS 队列解法（解法 1）。清晰易懂，是优先选择。
- 如果数据规模中等且需要最优效率：写DFS 解法（解法 2）。递归代码更简洁，但需注意递归深度。
- 注意特殊情况：
- 输入为
null的边界。 - 确保编号的范围不会超过
int取值范围（通常树的层级不会超过几十层）。
- 输入为
- 模板熟练度：
- BFS 模板：尽量减少额外的数据结构操作（比如
Pair）。 - DFS 模板：确保层编号和位编号一致处理。
- BFS 模板：尽量减少额外的数据结构操作（比如
通过以上解法分析与模板准备，可以快速完成这道题并 AC！