LeetCode 662 Maximum Width of Binary Tree 二叉树最大宽度BFS/DFS 索引编号与防溢出归一化全解leetcode1/leetcode 仓库实践【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 maximum-width-of-binary-tree.md 这篇题解文档展开系统讲解 LeetCode 662「二叉树的最大宽度」Maximum Width of Binary Tree的三种核心解法朴素 BFS、归一化 BFS防溢出优化与 DFS。你将掌握如何为二叉树节点按完全二叉树规则分配位置编号如何用rightmost - leftmost 1精确计算每层宽度以及如何通过每层起点归一化避免深层斜树场景下的整数溢出。文中所有算法均可在本仓库 python/0662-maximum-width-of-binary-tree.py、java/0662-maximum-width-of-binary-tree.java、kotlin/0662-maximum-width-of-binary-tree.kt 等源码中直接对照验证并配有 Python、Java、C、JavaScript、Go、Kotlin、Swift、Rust 八种语言的完整实现。问题定义什么是二叉树的最大宽度二叉树的宽度width定义为某一层中最左侧非空节点与最右侧非空节点之间的位置跨度其中包含中间的空节点null占位。最大宽度即所有层宽度的最大值。例如对如下二叉树1 / \ 3 2 / \ 5 9第 0 层只有根节点1宽度为 1第 1 层3与2紧邻宽度为 2第 2 层5位于最左9位于最右中间夹着两个空位因此该层宽度为4而不是 2。所以答案为 4。这个例子直观说明宽度不是该层非空节点个数而是最左与最右位置之间的距离 1中间的空节点必须计入。核心思想为节点分配位置编号要计算跨度需要给每个节点一个水平位置编号规则仿照完全二叉树的数组存储下标根节点位置为1任一节点位置为p时其左孩子位置为2 * p右孩子位置为2 * p 1。这与经典Tree Node Indexing技巧一致也是 maximum-width-of-binary-tree.md 在 Prerequisites 中强调的预备知识。有了编号后某层宽度 该层最后一个节点的编号 − 第一个节点的编号 1。前置知识Prerequisites在动手实现前需要熟练掌握以下四块基础缺一不可预备技能关键点二叉树基础Binary Tree Basics树的结构、节点定义、父子关系node.left/node.right广度优先搜索 BFS使用队列queue进行层序遍历逐层处理节点深度优先搜索 DFS递归遍历树携带层级与位置参数节点索引Tree Node Indexing完全二叉树下标映射左孩子2 * i右孩子2 * i 1原文档明确要求读者先具备以上能力本文将在此基础上把编号思想贯彻到 BFS 与 DFS 两种遍历范式之中。方法一BFS朴素版——逐层记录首尾编号直觉Intuition宽度的定义是最左与最右非空节点之间的距离含中间空节点。因此我们给每个节点分配位置编号根为1左孩子2 * p右孩子2 * p 1用 BFS 逐层推进每层用该层最后一个节点的编号 − 第一个节点的编号 1作为该层宽度全程取最大值。算法步骤Algorithm初始化res 0队列初始放入(root, 1, 0)三元组分别表示(node, position, level)用prevLevel与prevNum记录每一层第一个节点的层级与编号当队列非空时循环出队(node, num, level)若level prevLevel说明进入新的一层将prevLevel、prevNum更新为当前层级与编号更新res max(res, num - prevNum 1)若左孩子存在入队(left, 2 * num, level 1)若右孩子存在入队(right, 2 * num 1, level 1)返回res。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 q deque([(root, 1, 0)]) # [node, num, level] prevLevel, prevNum 0, 1 while q: node, num, level q.popleft() if level prevLevel: prevLevel level prevNum num res max(res, num - prevNum 1) if node.left: q.append((node.left, 2 * num, level 1)) if node.right: q.append((node.right, 2 * num 1, level 1)) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public int widthOfBinaryTree(TreeNode root) { if (root null) return 0; int res 0; QueueTuple queue new LinkedList(); queue.offer(new Tuple(root, 1, 0)); // [node, num, level] int prevLevel 0, prevNum 1; while (!queue.isEmpty()) { Tuple current queue.poll(); TreeNode node current.node; int num current.num; int level current.level; if (level prevLevel) { prevLevel level; prevNum num; } res Math.max(res, num - prevNum 1); if (node.left ! null) { queue.offer(new Tuple(node.left, 2 * num, level 1)); } if (node.right ! null) { queue.offer(new Tuple(node.right, 2 * num 1, level 1)); } } return res; } class Tuple { TreeNode node; int num, level; Tuple(TreeNode node, int num, int level) { this.node node; this.num num; this.level level; } } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { if (!root) return 0; int res 0; queuetupleTreeNode*, uint, int q; // [node, num, level] q.push({root, 1, 0}); int prevLevel 0, prevNum 1; while (!q.empty()) { auto [node, num, level] q.front(); q.pop(); if (level prevLevel) { prevLevel level; prevNum num; } res max(res, int(num - prevNum) 1); if (node-left) { q.push({node-left, 2 * num, level 1}); } if (node-right) { q.push({node-right, 2 * num 1, level 1}); } } return res; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { if (!root) return 0; let res 0n; const queue new Queue([[root, 1n, 0]]); // [node, num, level] let prevLevel 0, prevNum 1n; while (!queue.isEmpty()) { const [node, num, level] queue.pop(); if (level prevLevel) { prevLevel level; prevNum num; } res res num - prevNum 1n ? res : num - prevNum 1n; if (node.left) { queue.push([node.left, 2n * num, level 1]); } if (node.right) { queue.push([node.right, 2n * num 1n, level 1]); } } return Number(res); } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { if root nil { return 0 } res : 0 type item struct { node *TreeNode num uint64 level int } queue : []item{{root, 1, 0}} prevLevel : 0 var prevNum uint64 1 for len(queue) 0 { cur : queue[0] queue queue[1:] node, num, level : cur.node, cur.num, cur.level if level prevLevel { prevLevel level prevNum num } width : int(num - prevNum 1) if width res { res width } if node.Left ! nil { queue append(queue, item{node.Left, 2 * num, level 1}) } if node.Right ! nil { queue append(queue, item{node.Right, 2*num 1, level 1}) } } return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun widthOfBinaryTree(root: TreeNode?): Int { if (root null) return 0 var res 0 val queue ArrayDequeTripleTreeNode, Long, Int() queue.add(Triple(root, 1L, 0)) var prevLevel 0 var prevNum 1L while (queue.isNotEmpty()) { val (node, num, level) queue.removeFirst() if (level prevLevel) { prevLevel level prevNum num } res maxOf(res, (num - prevNum 1).toInt()) node.left?.let { queue.add(Triple(it, 2 * num, level 1)) } node.right?.let { queue.add(Triple(it, 2 * num 1, level 1)) } } return res } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func widthOfBinaryTree(_ root: TreeNode?) - Int { guard let root root else { return 0 } var res 0 var queue: [(TreeNode, UInt64, Int)] [(root, 1, 0)] var prevLevel 0 var prevNum: UInt64 1 while !queue.isEmpty { let (node, num, level) queue.removeFirst() if level prevLevel { prevLevel level prevNum num } res max(res, Int(num - prevNum 1)) if let left node.left { queue.append((left, 2 * num, level 1)) } if let right node.right { queue.append((right, 2 * num 1, level 1)) } } return res } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let root match root { Some(r) r, None return 0, }; let mut res: u64 0; // (node, num, level) let mut queue: VecDeque(RcRefCellTreeNode, u64, i32) VecDeque::new(); queue.push_back((root, 1, 0)); let mut prev_level 0; let mut prev_num: u64 1; while let Some((node, num, level)) queue.pop_front() { if level prev_level { prev_level level; prev_num num; } res res.max(num - prev_num 1); let node_ref node.borrow(); if let Some(ref left) node_ref.left { queue.push_back((Rc::clone(left), 2 * num, level 1)); } if let Some(ref right) node_ref.right { queue.push_back((Rc::clone(right), 2 * num 1, level 1)); } } res as i32 } }复杂度分析时间复杂度$O(n)$每个节点恰好入队、出队一次空间复杂度$O(n)$队列最多同时容纳一整层的节点最坏情况如满二叉树的最深层接近 $n$。仓库源码对照本仓库 java/0662-maximum-width-of-binary-tree.java 正是这一朴素 BFS 思路的落地实现它同样维护prevLevel/prevNum在level prevLevel时刷新每层起点并逐节点执行res Math.max(res, num - prevNum 1)kotlin/0662-maximum-width-of-binary-tree.kt 中的SolutionBFS 版本也完全一致。二者可直接与上面的伪代码逐行对应验证算法细节。方法二BFS最优版——每层起点归一化杜绝溢出直觉Intuition位置编号每下降一层就会翻倍左孩子2 * num右孩子2 * num 1。在深而斜的树skewed tree中编号会以指数速度增长很快溢出标准整数类型。解决办法是在每一层内部把所有编号减去该层第一个节点的编号起点进行归一化。归一化后编号始终保持小数值而每层宽度最右编号 − 最左编号 1的计算结果不受影响。算法步骤Algorithm初始化res 0队列初始放入(root, 0)当队列非空时循环记录start为当前层第一个节点的编号遍历当前层的每个节点用for i in range(len(q))界定一层计算归一化编号curNum num - start更新res max(res, curNum 1)左孩子入队(left, 2 * curNum)右孩子入队(right, 2 * curNum 1)返回res。注意子节点的编号基于归一化后的curNum计算而不是原始num这是本方法与朴素版的关键差异。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 q deque([(root, 0)]) while q: start q[0][1] for _ in range(len(q)): node, num q.popleft() curNum num - start res max(res, curNum 1) if node.left: q.append((node.left, 2 * curNum)) if node.right: q.append((node.right, 2 * curNum 1)) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public int widthOfBinaryTree(TreeNode root) { int res 0; QueuePairTreeNode, Integer q new LinkedList(); q.offer(new Pair(root, 0)); while (!q.isEmpty()) { int start q.peek().getValue(); for (int i q.size(); i 0; i--) { PairTreeNode, Integer pair q.poll(); TreeNode node pair.getKey(); int num pair.getValue() - start; res Math.max(res, num 1); if (node.left ! null) { q.offer(new Pair(node.left, 2 * num)); } if (node.right ! null) { q.offer(new Pair(node.right, 2 * num 1)); } } } return res; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { int res 0; queuepairTreeNode*, uint q; q.push({root, 0}); while (!q.empty()) { int start q.front().second; for (int i q.size(); i 0; --i) { auto [node, num] q.front(); q.pop(); uint curNum num - start; res max(res, int(curNum) 1); if (node-left) { q.push({node-left, 2 * curNum}); } if (node-right) { q.push({node-right, 2 * curNum 1}); } } } return res; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { let res 0; const q new Queue([[root, 0]]); while (!q.isEmpty()) { const start q.front()[1]; for (let i q.size(); i 0; i--) { const [node, num] q.pop(); const curNum num - start; res Math.max(res, curNum 1); if (node.left) { q.push([node.left, 2 * curNum]); } if (node.right) { q.push([node.right, 2 * curNum 1]); } } } return res; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { res : 0 type item struct { node *TreeNode num uint } queue : []item{{root, 0}} for len(queue) 0 { start : queue[0].num size : len(queue) for i : 0; i size; i { cur : queue[0] queue queue[1:] curNum : cur.num - start if int(curNum)1 res { res int(curNum) 1 } if cur.node.Left ! nil { queue append(queue, item{cur.node.Left, 2 * curNum}) } if cur.node.Right ! nil { queue append(queue, item{cur.node.Right, 2*curNum 1}) } } } return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun widthOfBinaryTree(root: TreeNode?): Int { var res 0 val queue ArrayDequePairTreeNode, Int() queue.add(root!! to 0) while (queue.isNotEmpty()) { val start queue.first().second val size queue.size repeat(size) { val (node, num) queue.removeFirst() val curNum num - start res maxOf(res, curNum 1) node.left?.let { queue.add(it to 2 * curNum) } node.right?.let { queue.add(it to 2 * curNum 1) } } } return res } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func widthOfBinaryTree(_ root: TreeNode?) - Int { guard let root root else { return 0 } var res 0 var queue: [(TreeNode, Int)] [(root, 0)] while !queue.isEmpty { let start queue.first!.1 let size queue.count for _ in 0..size { let (node, num) queue.removeFirst() let curNum num - start res max(res, curNum 1) if let left node.left { queue.append((left, 2 * curNum)) } if let right node.right { queue.append((right, 2 * curNum 1)) } } } return res } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let root match root { Some(r) r, None return 0, }; let mut res: u64 0; let mut queue: VecDeque(RcRefCellTreeNode, u64) VecDeque::new(); queue.push_back((root, 0)); while !queue.is_empty() { let start queue.front().unwrap().1; let size queue.len(); for _ in 0..size { let (node, num) queue.pop_front().unwrap(); let cur_num num - start; res res.max(cur_num 1); let node_ref node.borrow(); if let Some(ref left) node_ref.left { queue.push_back((Rc::clone(left), 2 * cur_num)); } if let Some(ref right) node_ref.right { queue.push_back((Rc::clone(right), 2 * cur_num 1)); } } } res as i32 } }复杂度分析时间复杂度$O(n)$同样每个节点只处理一次空间复杂度$O(n)$。与方法一相比复杂度量级相同但编号始终被限制在该层实际跨度内从根本上规避了深层斜树场景下的整数溢出问题这也是它被标记为Optimal的原因。仓库 python/0662-maximum-width-of-binary-tree.py 采用的正是这一归一化思路的变体它每层取leftIndex q[0][1]、rightIndex q[-1][1]直接以rightIndex - leftIndex 1求层宽等价于对每层起点做隐式归一化是工程实现上更简洁的写法。方法三DFS递归——哈希表记录每层首节点直觉Intuition宽度计算不需要逐层顺序也可以借助 DFS 完成递归过程中记录每个层级第一个被访问节点的位置。首次到达某层时把该节点位置记为first[level]之后该层任意节点与first[level]的位置差 1 即为当前跨度全程取最大。子节点位置同样做归一化以避免溢出。算法步骤Algorithm维护哈希表firstfirst[level]存储该层第一个被访问节点的位置定义递归函数dfs(node, level, curNum)若node为空直接返回若level尚未出现在first中设置first[level] curNum更新res max(res, curNum - first[level] 1)递归左孩子dfs(node.left, level 1, 2 * (curNum - first[level]))递归右孩子dfs(node.right, level 1, 2 * (curNum - first[level]) 1)调用dfs(root, 0, 0)返回res。注意递归传参的子节点编号是基于curNum - first[level]已归一化这也是防溢出的关键。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: first {} res 0 def dfs(node, level, num): nonlocal res if not node: return if level not in first: first[level] num res max(res, num - first[level] 1) dfs(node.left, level 1, 2 * num) dfs(node.right, level 1, 2 * num 1) dfs(root, 0, 0) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { private MapInteger, Integer first; public int widthOfBinaryTree(TreeNode root) { first new HashMap(); int[] res new int[1]; dfs(root, 0, 0, res); return res[0]; } private void dfs(TreeNode node, int level, int num, int[] res) { if (node null) { return; } first.putIfAbsent(level, num); res[0] Math.max(res[0], num - first.get(level) 1); dfs(node.left, level 1, 2 * num, res); dfs(node.right, level 1, 2 * num 1, res); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { unordered_mapint, unsigned long long first; public: int widthOfBinaryTree(TreeNode* root) { unsigned long long res 0; dfs(root, 0, 0, res); return int(res); } private: void dfs(TreeNode* node, int level, unsigned long long num, unsigned long long res) { if (!node) { return; } if (!first.count(level)) { first[level] num; } res max(res, num - first[level] 1); dfs(node-left, level 1, 2 * (num - first[level]), res); dfs(node-right, level 1, 2 * (num - first[level]) 1, res); } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { const first new Map(); let res 0; const dfs (node, level, curNum) { if (!node) return; if (!first.has(level)) { first.set(level, curNum); } res Math.max(res, curNum - first.get(level) 1); dfs(node.left, level 1, 2 * (curNum - first.get(level))); dfs(node.right, level 1, 2 * (curNum - first.get(level)) 1); }; dfs(root, 0, 0); return res; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { first : make(map[int]int) res : 0 var dfs func(node *TreeNode, level, curNum int) dfs func(node *TreeNode, level, curNum int) { if node nil { return } if _, ok : first[level]; !ok { first[level] curNum } width : curNum - first[level] 1 if width res { res width } dfs(node.Left, level1, 2*(curNum-first[level])) dfs(node.Right, level1, 2*(curNum-first[level])1) } dfs(root, 0, 0) return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { private val first mutableMapOfInt, Int() private var res 0 fun widthOfBinaryTree(root: TreeNode?): Int { first.clear() res 0 dfs(root, 0, 0) return res } private fun dfs(node: TreeNode?, level: Int, curNum: Int) { if (node null) return if (level !in first) { first[level] curNum } res maxOf(res, curNum - first[level]!! 1) dfs(node.left, level 1, 2 * (curNum - first[level]!!)) dfs(node.right, level 1, 2 * (curNum - first[level]!!) 1) } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { private var first [Int: Int]() private var res 0 func widthOfBinaryTree(_ root: TreeNode?) - Int { first [:] res 0 dfs(root, 0, 0) return res } private func dfs(_ node: TreeNode?, _ level: Int, _ curNum: Int) { guard let node node else { return } if first[level] nil { first[level] curNum } res max(res, curNum - first[level]! 1) dfs(node.left, level 1, 2 * (curNum - first[level]!)) dfs(node.right, level 1, 2 * (curNum - first[level]!) 1) } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let mut first: HashMapi32, u64 HashMap::new(); let mut res: u64 0; fn dfs( node: OptionRcRefCellTreeNode, level: i32, cur_num: u64, first: mut HashMapi32, u64, res: mut u64, ) { let node match node { Some(n) n, None return, }; first.entry(level).or_insert(cur_num); let f *first.get(level).unwrap(); *res (*res).max(cur_num - f 1); let node_ref node.borrow(); dfs(node_ref.left, level 1, 2 * (cur_num - f), first, res); dfs(node_ref.right, level 1, 2 * (cur_num - f) 1, first, res); } dfs(root, 0, 0, mut first, mut res); res as i32 } }复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$哈希表存储每层首节点位置 递归调用栈深度斜树场景栈深为 $O(n)$。仓库源码对照kotlin/0662-maximum-width-of-binary-tree.kt 中的第二个Solution标注 DFS solution与本节完全一致用levelMap即first记录每层首个位置width maxOf(width, pos - levelMap[depth]!! 1)并以2 * pos/2 * pos 1递归左右子树。同一个.kt文件同时给出 BFS 与 DFS 两种实现可直接对照两种范式在 Kotlin 中的写法差异。三种解法横向对比解法遍历方式编号策略防溢出时间复杂度空间复杂度适用场景BFS朴素版队列逐层全局编号根为 1需借助uint/BigInt等大类型$O(n)$$O(n)$树深度有限、编号不会溢出的场景BFS最优版队列逐层每层起点归一化天然规避$O(n)$$O(n)$通用首选深层斜树也能安全运行DFS递归 哈希表每层首节点归一化天然规避$O(n)$$O(n)$偏好递归写法、或与后序处理结合时三种方法时间复杂度均为 $O(n)$核心差异在于编号是否归一化以及遍历顺序。Common Pitfalls三个高频易错点原文档在末尾专门列出三类常见错误这里逐一展开说明1. 位置编号的整数溢出Integer Overflow from Position Numbers编号每层翻倍左孩子2 * num右孩子2 * num 1。在深度很大的斜树中编号呈指数增长极易溢出标准 32 位整数。原文档给出的应对策略有三使用更大的整数类型C 用unsigned long long见 maximum-width-of-binary-tree.md 中 DFS 版本的unordered_mapint, unsigned long long first、JavaScript 用BigInt朴素 BFS 版中以0n、1n、2n * num参与运算或采用每层起点归一化减去该层首节点编号后再计算子节点编号即方法二、方法三的做法从根本上让编号保持在层内跨度量级。2. 宽度少算 1Miscounting the Width宽度是最左与最右位置之间含两端的节点跨度公式必须是rightmost - leftmost 1。若漏掉 1例如单节点层会得到0而非1整棵树只有一个节点时答案将错误地为 0。实现时务必在max更新处保留 1。3. BFS 层边界追踪错误Incorrect Level Tracking in BFS逐层处理时必须准确识别每一层的第一个节点并记录其编号作为起点朴素版通过level prevLevel判断进入新层并刷新prevNum最优版通过start q[0][1]结合for _ in range(len(q))界定当前层。如果层边界判断失误、或在进入新层时未能更新起点宽度计算就会整体偏移、结果错误。延伸阅读与仓库导航题解原文articles/maximum-width-of-binary-tree.md包含全部八种语言的完整实现与复杂度分析Python 实现python/0662-maximum-width-of-binary-tree.pyJava 实现java/0662-maximum-width-of-binary-tree.javaKotlin 实现BFS DFS 双解法kotlin/0662-maximum-width-of-binary-tree.kt题目完成情况总览README.md其中记录了 0662 题在 Java、Kotlin、Python 等语言的实现状态本文所涉及的节点编号 层宽计算思想与 level-order-traversal-of-binary-tree.md、binary-tree-vertical-order-traversal.md 等仓库内二叉树题解同属位置编号 遍历技术族可交叉阅读加深理解。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 662 Maximum Width of Binary Tree 二叉树最大宽度：BFS/DFS 索引编号与防溢出归一化全解（leetcode1/leetcode 仓库实践）
LeetCode 662 Maximum Width of Binary Tree 二叉树最大宽度BFS/DFS 索引编号与防溢出归一化全解leetcode1/leetcode 仓库实践【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 maximum-width-of-binary-tree.md 这篇题解文档展开系统讲解 LeetCode 662「二叉树的最大宽度」Maximum Width of Binary Tree的三种核心解法朴素 BFS、归一化 BFS防溢出优化与 DFS。你将掌握如何为二叉树节点按完全二叉树规则分配位置编号如何用rightmost - leftmost 1精确计算每层宽度以及如何通过每层起点归一化避免深层斜树场景下的整数溢出。文中所有算法均可在本仓库 python/0662-maximum-width-of-binary-tree.py、java/0662-maximum-width-of-binary-tree.java、kotlin/0662-maximum-width-of-binary-tree.kt 等源码中直接对照验证并配有 Python、Java、C、JavaScript、Go、Kotlin、Swift、Rust 八种语言的完整实现。问题定义什么是二叉树的最大宽度二叉树的宽度width定义为某一层中最左侧非空节点与最右侧非空节点之间的位置跨度其中包含中间的空节点null占位。最大宽度即所有层宽度的最大值。例如对如下二叉树1 / \ 3 2 / \ 5 9第 0 层只有根节点1宽度为 1第 1 层3与2紧邻宽度为 2第 2 层5位于最左9位于最右中间夹着两个空位因此该层宽度为4而不是 2。所以答案为 4。这个例子直观说明宽度不是该层非空节点个数而是最左与最右位置之间的距离 1中间的空节点必须计入。核心思想为节点分配位置编号要计算跨度需要给每个节点一个水平位置编号规则仿照完全二叉树的数组存储下标根节点位置为1任一节点位置为p时其左孩子位置为2 * p右孩子位置为2 * p 1。这与经典Tree Node Indexing技巧一致也是 maximum-width-of-binary-tree.md 在 Prerequisites 中强调的预备知识。有了编号后某层宽度 该层最后一个节点的编号 − 第一个节点的编号 1。前置知识Prerequisites在动手实现前需要熟练掌握以下四块基础缺一不可预备技能关键点二叉树基础Binary Tree Basics树的结构、节点定义、父子关系node.left/node.right广度优先搜索 BFS使用队列queue进行层序遍历逐层处理节点深度优先搜索 DFS递归遍历树携带层级与位置参数节点索引Tree Node Indexing完全二叉树下标映射左孩子2 * i右孩子2 * i 1原文档明确要求读者先具备以上能力本文将在此基础上把编号思想贯彻到 BFS 与 DFS 两种遍历范式之中。方法一BFS朴素版——逐层记录首尾编号直觉Intuition宽度的定义是最左与最右非空节点之间的距离含中间空节点。因此我们给每个节点分配位置编号根为1左孩子2 * p右孩子2 * p 1用 BFS 逐层推进每层用该层最后一个节点的编号 − 第一个节点的编号 1作为该层宽度全程取最大值。算法步骤Algorithm初始化res 0队列初始放入(root, 1, 0)三元组分别表示(node, position, level)用prevLevel与prevNum记录每一层第一个节点的层级与编号当队列非空时循环出队(node, num, level)若level prevLevel说明进入新的一层将prevLevel、prevNum更新为当前层级与编号更新res max(res, num - prevNum 1)若左孩子存在入队(left, 2 * num, level 1)若右孩子存在入队(right, 2 * num 1, level 1)返回res。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 q deque([(root, 1, 0)]) # [node, num, level] prevLevel, prevNum 0, 1 while q: node, num, level q.popleft() if level prevLevel: prevLevel level prevNum num res max(res, num - prevNum 1) if node.left: q.append((node.left, 2 * num, level 1)) if node.right: q.append((node.right, 2 * num 1, level 1)) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public int widthOfBinaryTree(TreeNode root) { if (root null) return 0; int res 0; QueueTuple queue new LinkedList(); queue.offer(new Tuple(root, 1, 0)); // [node, num, level] int prevLevel 0, prevNum 1; while (!queue.isEmpty()) { Tuple current queue.poll(); TreeNode node current.node; int num current.num; int level current.level; if (level prevLevel) { prevLevel level; prevNum num; } res Math.max(res, num - prevNum 1); if (node.left ! null) { queue.offer(new Tuple(node.left, 2 * num, level 1)); } if (node.right ! null) { queue.offer(new Tuple(node.right, 2 * num 1, level 1)); } } return res; } class Tuple { TreeNode node; int num, level; Tuple(TreeNode node, int num, int level) { this.node node; this.num num; this.level level; } } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { if (!root) return 0; int res 0; queuetupleTreeNode*, uint, int q; // [node, num, level] q.push({root, 1, 0}); int prevLevel 0, prevNum 1; while (!q.empty()) { auto [node, num, level] q.front(); q.pop(); if (level prevLevel) { prevLevel level; prevNum num; } res max(res, int(num - prevNum) 1); if (node-left) { q.push({node-left, 2 * num, level 1}); } if (node-right) { q.push({node-right, 2 * num 1, level 1}); } } return res; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { if (!root) return 0; let res 0n; const queue new Queue([[root, 1n, 0]]); // [node, num, level] let prevLevel 0, prevNum 1n; while (!queue.isEmpty()) { const [node, num, level] queue.pop(); if (level prevLevel) { prevLevel level; prevNum num; } res res num - prevNum 1n ? res : num - prevNum 1n; if (node.left) { queue.push([node.left, 2n * num, level 1]); } if (node.right) { queue.push([node.right, 2n * num 1n, level 1]); } } return Number(res); } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { if root nil { return 0 } res : 0 type item struct { node *TreeNode num uint64 level int } queue : []item{{root, 1, 0}} prevLevel : 0 var prevNum uint64 1 for len(queue) 0 { cur : queue[0] queue queue[1:] node, num, level : cur.node, cur.num, cur.level if level prevLevel { prevLevel level prevNum num } width : int(num - prevNum 1) if width res { res width } if node.Left ! nil { queue append(queue, item{node.Left, 2 * num, level 1}) } if node.Right ! nil { queue append(queue, item{node.Right, 2*num 1, level 1}) } } return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun widthOfBinaryTree(root: TreeNode?): Int { if (root null) return 0 var res 0 val queue ArrayDequeTripleTreeNode, Long, Int() queue.add(Triple(root, 1L, 0)) var prevLevel 0 var prevNum 1L while (queue.isNotEmpty()) { val (node, num, level) queue.removeFirst() if (level prevLevel) { prevLevel level prevNum num } res maxOf(res, (num - prevNum 1).toInt()) node.left?.let { queue.add(Triple(it, 2 * num, level 1)) } node.right?.let { queue.add(Triple(it, 2 * num 1, level 1)) } } return res } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func widthOfBinaryTree(_ root: TreeNode?) - Int { guard let root root else { return 0 } var res 0 var queue: [(TreeNode, UInt64, Int)] [(root, 1, 0)] var prevLevel 0 var prevNum: UInt64 1 while !queue.isEmpty { let (node, num, level) queue.removeFirst() if level prevLevel { prevLevel level prevNum num } res max(res, Int(num - prevNum 1)) if let left node.left { queue.append((left, 2 * num, level 1)) } if let right node.right { queue.append((right, 2 * num 1, level 1)) } } return res } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let root match root { Some(r) r, None return 0, }; let mut res: u64 0; // (node, num, level) let mut queue: VecDeque(RcRefCellTreeNode, u64, i32) VecDeque::new(); queue.push_back((root, 1, 0)); let mut prev_level 0; let mut prev_num: u64 1; while let Some((node, num, level)) queue.pop_front() { if level prev_level { prev_level level; prev_num num; } res res.max(num - prev_num 1); let node_ref node.borrow(); if let Some(ref left) node_ref.left { queue.push_back((Rc::clone(left), 2 * num, level 1)); } if let Some(ref right) node_ref.right { queue.push_back((Rc::clone(right), 2 * num 1, level 1)); } } res as i32 } }复杂度分析时间复杂度$O(n)$每个节点恰好入队、出队一次空间复杂度$O(n)$队列最多同时容纳一整层的节点最坏情况如满二叉树的最深层接近 $n$。仓库源码对照本仓库 java/0662-maximum-width-of-binary-tree.java 正是这一朴素 BFS 思路的落地实现它同样维护prevLevel/prevNum在level prevLevel时刷新每层起点并逐节点执行res Math.max(res, num - prevNum 1)kotlin/0662-maximum-width-of-binary-tree.kt 中的SolutionBFS 版本也完全一致。二者可直接与上面的伪代码逐行对应验证算法细节。方法二BFS最优版——每层起点归一化杜绝溢出直觉Intuition位置编号每下降一层就会翻倍左孩子2 * num右孩子2 * num 1。在深而斜的树skewed tree中编号会以指数速度增长很快溢出标准整数类型。解决办法是在每一层内部把所有编号减去该层第一个节点的编号起点进行归一化。归一化后编号始终保持小数值而每层宽度最右编号 − 最左编号 1的计算结果不受影响。算法步骤Algorithm初始化res 0队列初始放入(root, 0)当队列非空时循环记录start为当前层第一个节点的编号遍历当前层的每个节点用for i in range(len(q))界定一层计算归一化编号curNum num - start更新res max(res, curNum 1)左孩子入队(left, 2 * curNum)右孩子入队(right, 2 * curNum 1)返回res。注意子节点的编号基于归一化后的curNum计算而不是原始num这是本方法与朴素版的关键差异。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 q deque([(root, 0)]) while q: start q[0][1] for _ in range(len(q)): node, num q.popleft() curNum num - start res max(res, curNum 1) if node.left: q.append((node.left, 2 * curNum)) if node.right: q.append((node.right, 2 * curNum 1)) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public int widthOfBinaryTree(TreeNode root) { int res 0; QueuePairTreeNode, Integer q new LinkedList(); q.offer(new Pair(root, 0)); while (!q.isEmpty()) { int start q.peek().getValue(); for (int i q.size(); i 0; i--) { PairTreeNode, Integer pair q.poll(); TreeNode node pair.getKey(); int num pair.getValue() - start; res Math.max(res, num 1); if (node.left ! null) { q.offer(new Pair(node.left, 2 * num)); } if (node.right ! null) { q.offer(new Pair(node.right, 2 * num 1)); } } } return res; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { int res 0; queuepairTreeNode*, uint q; q.push({root, 0}); while (!q.empty()) { int start q.front().second; for (int i q.size(); i 0; --i) { auto [node, num] q.front(); q.pop(); uint curNum num - start; res max(res, int(curNum) 1); if (node-left) { q.push({node-left, 2 * curNum}); } if (node-right) { q.push({node-right, 2 * curNum 1}); } } } return res; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { let res 0; const q new Queue([[root, 0]]); while (!q.isEmpty()) { const start q.front()[1]; for (let i q.size(); i 0; i--) { const [node, num] q.pop(); const curNum num - start; res Math.max(res, curNum 1); if (node.left) { q.push([node.left, 2 * curNum]); } if (node.right) { q.push([node.right, 2 * curNum 1]); } } } return res; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { res : 0 type item struct { node *TreeNode num uint } queue : []item{{root, 0}} for len(queue) 0 { start : queue[0].num size : len(queue) for i : 0; i size; i { cur : queue[0] queue queue[1:] curNum : cur.num - start if int(curNum)1 res { res int(curNum) 1 } if cur.node.Left ! nil { queue append(queue, item{cur.node.Left, 2 * curNum}) } if cur.node.Right ! nil { queue append(queue, item{cur.node.Right, 2*curNum 1}) } } } return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun widthOfBinaryTree(root: TreeNode?): Int { var res 0 val queue ArrayDequePairTreeNode, Int() queue.add(root!! to 0) while (queue.isNotEmpty()) { val start queue.first().second val size queue.size repeat(size) { val (node, num) queue.removeFirst() val curNum num - start res maxOf(res, curNum 1) node.left?.let { queue.add(it to 2 * curNum) } node.right?.let { queue.add(it to 2 * curNum 1) } } } return res } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func widthOfBinaryTree(_ root: TreeNode?) - Int { guard let root root else { return 0 } var res 0 var queue: [(TreeNode, Int)] [(root, 0)] while !queue.isEmpty { let start queue.first!.1 let size queue.count for _ in 0..size { let (node, num) queue.removeFirst() let curNum num - start res max(res, curNum 1) if let left node.left { queue.append((left, 2 * curNum)) } if let right node.right { queue.append((right, 2 * curNum 1)) } } } return res } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let root match root { Some(r) r, None return 0, }; let mut res: u64 0; let mut queue: VecDeque(RcRefCellTreeNode, u64) VecDeque::new(); queue.push_back((root, 0)); while !queue.is_empty() { let start queue.front().unwrap().1; let size queue.len(); for _ in 0..size { let (node, num) queue.pop_front().unwrap(); let cur_num num - start; res res.max(cur_num 1); let node_ref node.borrow(); if let Some(ref left) node_ref.left { queue.push_back((Rc::clone(left), 2 * cur_num)); } if let Some(ref right) node_ref.right { queue.push_back((Rc::clone(right), 2 * cur_num 1)); } } } res as i32 } }复杂度分析时间复杂度$O(n)$同样每个节点只处理一次空间复杂度$O(n)$。与方法一相比复杂度量级相同但编号始终被限制在该层实际跨度内从根本上规避了深层斜树场景下的整数溢出问题这也是它被标记为Optimal的原因。仓库 python/0662-maximum-width-of-binary-tree.py 采用的正是这一归一化思路的变体它每层取leftIndex q[0][1]、rightIndex q[-1][1]直接以rightIndex - leftIndex 1求层宽等价于对每层起点做隐式归一化是工程实现上更简洁的写法。方法三DFS递归——哈希表记录每层首节点直觉Intuition宽度计算不需要逐层顺序也可以借助 DFS 完成递归过程中记录每个层级第一个被访问节点的位置。首次到达某层时把该节点位置记为first[level]之后该层任意节点与first[level]的位置差 1 即为当前跨度全程取最大。子节点位置同样做归一化以避免溢出。算法步骤Algorithm维护哈希表firstfirst[level]存储该层第一个被访问节点的位置定义递归函数dfs(node, level, curNum)若node为空直接返回若level尚未出现在first中设置first[level] curNum更新res max(res, curNum - first[level] 1)递归左孩子dfs(node.left, level 1, 2 * (curNum - first[level]))递归右孩子dfs(node.right, level 1, 2 * (curNum - first[level]) 1)调用dfs(root, 0, 0)返回res。注意递归传参的子节点编号是基于curNum - first[level]已归一化这也是防溢出的关键。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) - int: first {} res 0 def dfs(node, level, num): nonlocal res if not node: return if level not in first: first[level] num res max(res, num - first[level] 1) dfs(node.left, level 1, 2 * num) dfs(node.right, level 1, 2 * num 1) dfs(root, 0, 0) return res/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { private MapInteger, Integer first; public int widthOfBinaryTree(TreeNode root) { first new HashMap(); int[] res new int[1]; dfs(root, 0, 0, res); return res[0]; } private void dfs(TreeNode node, int level, int num, int[] res) { if (node null) { return; } first.putIfAbsent(level, num); res[0] Math.max(res[0], num - first.get(level) 1); dfs(node.left, level 1, 2 * num, res); dfs(node.right, level 1, 2 * num 1, res); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { unordered_mapint, unsigned long long first; public: int widthOfBinaryTree(TreeNode* root) { unsigned long long res 0; dfs(root, 0, 0, res); return int(res); } private: void dfs(TreeNode* node, int level, unsigned long long num, unsigned long long res) { if (!node) { return; } if (!first.count(level)) { first[level] num; } res max(res, num - first[level] 1); dfs(node-left, level 1, 2 * (num - first[level]), res); dfs(node-right, level 1, 2 * (num - first[level]) 1, res); } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number} */ widthOfBinaryTree(root) { const first new Map(); let res 0; const dfs (node, level, curNum) { if (!node) return; if (!first.has(level)) { first.set(level, curNum); } res Math.max(res, curNum - first.get(level) 1); dfs(node.left, level 1, 2 * (curNum - first.get(level))); dfs(node.right, level 1, 2 * (curNum - first.get(level)) 1); }; dfs(root, 0, 0); return res; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { first : make(map[int]int) res : 0 var dfs func(node *TreeNode, level, curNum int) dfs func(node *TreeNode, level, curNum int) { if node nil { return } if _, ok : first[level]; !ok { first[level] curNum } width : curNum - first[level] 1 if width res { res width } dfs(node.Left, level1, 2*(curNum-first[level])) dfs(node.Right, level1, 2*(curNum-first[level])1) } dfs(root, 0, 0) return res }/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { private val first mutableMapOfInt, Int() private var res 0 fun widthOfBinaryTree(root: TreeNode?): Int { first.clear() res 0 dfs(root, 0, 0) return res } private fun dfs(node: TreeNode?, level: Int, curNum: Int) { if (node null) return if (level !in first) { first[level] curNum } res maxOf(res, curNum - first[level]!! 1) dfs(node.left, level 1, 2 * (curNum - first[level]!!)) dfs(node.right, level 1, 2 * (curNum - first[level]!!) 1) } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { private var first [Int: Int]() private var res 0 func widthOfBinaryTree(_ root: TreeNode?) - Int { first [:] res 0 dfs(root, 0, 0) return res } private func dfs(_ node: TreeNode?, _ level: Int, _ curNum: Int) { guard let node node else { return } if first[level] nil { first[level] curNum } res max(res, curNum - first[level]! 1) dfs(node.left, level 1, 2 * (curNum - first[level]!)) dfs(node.right, level 1, 2 * (curNum - first[level]!) 1) } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn width_of_binary_tree(root: OptionRcRefCellTreeNode) - i32 { let mut first: HashMapi32, u64 HashMap::new(); let mut res: u64 0; fn dfs( node: OptionRcRefCellTreeNode, level: i32, cur_num: u64, first: mut HashMapi32, u64, res: mut u64, ) { let node match node { Some(n) n, None return, }; first.entry(level).or_insert(cur_num); let f *first.get(level).unwrap(); *res (*res).max(cur_num - f 1); let node_ref node.borrow(); dfs(node_ref.left, level 1, 2 * (cur_num - f), first, res); dfs(node_ref.right, level 1, 2 * (cur_num - f) 1, first, res); } dfs(root, 0, 0, mut first, mut res); res as i32 } }复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$哈希表存储每层首节点位置 递归调用栈深度斜树场景栈深为 $O(n)$。仓库源码对照kotlin/0662-maximum-width-of-binary-tree.kt 中的第二个Solution标注 DFS solution与本节完全一致用levelMap即first记录每层首个位置width maxOf(width, pos - levelMap[depth]!! 1)并以2 * pos/2 * pos 1递归左右子树。同一个.kt文件同时给出 BFS 与 DFS 两种实现可直接对照两种范式在 Kotlin 中的写法差异。三种解法横向对比解法遍历方式编号策略防溢出时间复杂度空间复杂度适用场景BFS朴素版队列逐层全局编号根为 1需借助uint/BigInt等大类型$O(n)$$O(n)$树深度有限、编号不会溢出的场景BFS最优版队列逐层每层起点归一化天然规避$O(n)$$O(n)$通用首选深层斜树也能安全运行DFS递归 哈希表每层首节点归一化天然规避$O(n)$$O(n)$偏好递归写法、或与后序处理结合时三种方法时间复杂度均为 $O(n)$核心差异在于编号是否归一化以及遍历顺序。Common Pitfalls三个高频易错点原文档在末尾专门列出三类常见错误这里逐一展开说明1. 位置编号的整数溢出Integer Overflow from Position Numbers编号每层翻倍左孩子2 * num右孩子2 * num 1。在深度很大的斜树中编号呈指数增长极易溢出标准 32 位整数。原文档给出的应对策略有三使用更大的整数类型C 用unsigned long long见 maximum-width-of-binary-tree.md 中 DFS 版本的unordered_mapint, unsigned long long first、JavaScript 用BigInt朴素 BFS 版中以0n、1n、2n * num参与运算或采用每层起点归一化减去该层首节点编号后再计算子节点编号即方法二、方法三的做法从根本上让编号保持在层内跨度量级。2. 宽度少算 1Miscounting the Width宽度是最左与最右位置之间含两端的节点跨度公式必须是rightmost - leftmost 1。若漏掉 1例如单节点层会得到0而非1整棵树只有一个节点时答案将错误地为 0。实现时务必在max更新处保留 1。3. BFS 层边界追踪错误Incorrect Level Tracking in BFS逐层处理时必须准确识别每一层的第一个节点并记录其编号作为起点朴素版通过level prevLevel判断进入新层并刷新prevNum最优版通过start q[0][1]结合for _ in range(len(q))界定当前层。如果层边界判断失误、或在进入新层时未能更新起点宽度计算就会整体偏移、结果错误。延伸阅读与仓库导航题解原文articles/maximum-width-of-binary-tree.md包含全部八种语言的完整实现与复杂度分析Python 实现python/0662-maximum-width-of-binary-tree.pyJava 实现java/0662-maximum-width-of-binary-tree.javaKotlin 实现BFS DFS 双解法kotlin/0662-maximum-width-of-binary-tree.kt题目完成情况总览README.md其中记录了 0662 题在 Java、Kotlin、Python 等语言的实现状态本文所涉及的节点编号 层宽计算思想与 level-order-traversal-of-binary-tree.md、binary-tree-vertical-order-traversal.md 等仓库内二叉树题解同属位置编号 遍历技术族可交叉阅读加深理解。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考