Leetcode 662: 二叉树最大宽度

Leetcode 662: 二叉树最大宽度 是一道考察树的层序遍历和位编号思想的经典题目。其目标是找到二叉树的每一层的最大宽度，宽度定义为：最左节点和最右节点间的节点数（包含这两个节点，中间可以有空节点）。

题目描述

给定一个二叉树的根节点 root，返回其最大宽度。
“宽度”定义为：
- 每层最左节点（即层级中最左非空节点）到最右节点之间节点的数目。
- 如果同一层只有一个非空节点，则宽度为 1。

解法 1：层序遍历 + 队列 (广度优先搜索 BFS)

思路

维护位置信息：
- 使用广度优先遍历 BFS，同时为每个节点分配一个基于完全二叉树的编号。根节点的编号为 1，左孩子为 2 * x，右孩子为 2 * x + 1。
- 每层的宽度可通过计算该层最右节点和最左节点对应编号的差值 width = right - left + 1。
层序遍历逐层更新最大宽度：
- 使用一个队列，存储每层节点和它们的编号 (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);// 当前宽度 = 当前节点的编号 - 当前层最左编号 + 1int 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 模板：确保层编号和位编号一致处理。