目录
题目
-
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点， 这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
题解：BFS
- 从根节点开始，逐层遍历每个节点。对于每个节点，如果其左子节点存在，则将左子节点加入队列；如果左子节点不存在，则创建一个值为0的新节点，并将其作为当前节点的左子节点添加到二叉树中。同样地处理右子树。然后，记录每一层的节点个数，更新最大宽度 m 的值为当前层的节点个数 size 和 m 中的较大值。最终返回最大宽度 m。
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
#如果谁的孩子是空就给创一个值为0的结点，用BFS计算每一层多少个结点，返回最大那个
if not root:
return 0
q=[root]
m=0# 最大宽度
while q:
size=len(q)
m=max(m,size)# 更新最大宽度
for _ in range(size):
cur=q.pop(0)# 弹出当前节点
if cur.left:# 如果有左子节点，将左子节点加入队列
q.append(cur.left)
else:# 如果没有左子节点，创建一个值为0的左子节点，并加入队列
new=TreeNode(0)
cur.left=new
q.append(cur.left)
if cur.right:# 如果有右子节点，将右子节点加入队列
q.append(cur.right)
else:# 如果没有右子节点，创建一个值为0的右子节点，并加入队列
new=TreeNode(0)
cur.right=new
q.append(cur.right)
return m# 返回最大宽度
- 超出时间限制
- 存在问题：对于示例3会给第二层都加上值为0的节点，和最后返回的结果不一样
正解：优化
- 上文新创节点实在不明智，这里直接用节点的位置索引，每一层的结束索引-开始索引+1则为该层的宽度，更新最大宽度，返回即可。
from collections import deque
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([(root, 0)]) # 使用双端队列存储节点及其对应的位置索引
max_width = 0
while q:
level_size = len(q) # 当前层的节点数量
_, start = q[0] # 等于start = q[0][1]当前层最左侧的节点的位置索引,不需要节点本身，用_占位，q为元组
_, end = q[-1] # end = q[-1][1]当前层最右侧的节点的位置索引
max_width = max(max_width, end - start + 1) # 更新最大宽度
for _ in range(level_size):
node, index = q.popleft() # 从左侧弹出节点及其位置索引
# 处理左子节点
if node.left:
q.append((node.left, 2 * index)) # 左子节点的位置索引为当前节点的位置索引乘以2
# 处理右子节点
if node.right:
q.append((node.right, 2 * index + 1)) # 右子节点的位置索引为当前节点的位置索引乘以2加1
return max_width # 返回最大宽度