Leetcode662:二叉树最大宽度

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 puteIfAbsent(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 模板：确保层编号和位编号一致处理。

通过以上解法分析与模板准备，可以快速完成这道题并 AC！