| 题目链接 | 662. 二叉树最大宽度 |
|---|---|
| 思路 | BFS+层次遍历 |
| 题解链接 | 官方题解 |
| 关键点 | 与传统层次遍历的差异点：为节点进行编码，最大宽度为队列中最后节点与最初节点之间的节点数量 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
answer = 1
q = [(root, 1)]
while q:
answer = max(answer, 1 + q[-1][1] - q[0][1])
new_q = []
for node, index in q:
if node.left: new_q.append((node.left, 2*index))
if node.right: new_q.append((node.right, 2*index+1))
q = new_q
return answer