| 题目链接 | 662. 二叉树最大宽度 |
|---|---|
| 思路 | BFS+层次遍历 |
| 题解链接 | 官方题解 |
| 关键点 | 与传统层次遍历的差异点：为节点进行编码，最大宽度为队列中最后节点与最初节点之间的节点数量 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:answer = 1q = [(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_qreturn answer
