LeetCode 题解工作台
二叉树最大宽度
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。 …
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
对节点进行编号，初始根节点编号为 。 对于一个编号为 `i` 的节点，它的左节点编号为 `i<<1`，右节点编号为 `i<<1|1`。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9] 输出：4 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7] 输出：7 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5] 输出：2 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是
[1, 3000] -100 <= Node.val <= 100
解题思路
方法一：BFS
对节点进行编号，初始根节点编号为 。
对于一个编号为 i 的节点，它的左节点编号为 i<<1，右节点编号为 i<<1|1。
采用 BFS 进行层序遍历，求每层的宽度时，用该层的最大节点编号减去最小节点编号再加一即可。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
q = deque([(root, 1)])
while q:
ans = max(ans, q[-1][1] - q[0][1] + 1)
for _ in range(len(q)):
root, i = q.popleft()
if root.left:
q.append((root.left, i << 1))
if root.right:
q.append((root.right, i << 1 | 1))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of nodes processed during the traversal, typically O(n) where n is the number of nodes. Space complexity is O(n) due to the queue used for level-order traversal, which holds the nodes at each level. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if the candidate can effectively apply breadth-first search (BFS) in a tree problem.
- question_mark
Assesses understanding of level-order traversal and index tracking.
- question_mark
Evaluates the ability to handle edge cases like sparse trees or deep binary trees.
常见陷阱
外企场景- error
Not accounting for null nodes between the non-null nodes at each level.
- error
Misunderstanding the problem by only counting nodes, instead of considering positions in a complete binary tree.
- error
Failing to maintain accurate indices when nodes are missing on a level, which may lead to incorrect width calculations.
进阶变体
外企场景- arrow_right_alt
Calculate the width of a binary tree with missing nodes, ensuring that null nodes are counted in the width.
- arrow_right_alt
Solve this problem with an iterative approach using a queue, rather than a recursive one.
- arrow_right_alt
Optimize the space complexity by using alternative data structures or modifying the traversal approach.