题解 | #牛群的最大宽度#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxWidthOfCows(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        
        max_width = 0#用于存储最大宽度
        queue =[(root,1)] #使用队列保存节点和其位置信息，初始位置为1

        while queue:
            level_length = len(queue) #当前节点的数量
            left_pos=queue[0][1] #最左节点的位置

            #遍历当前层的节点
            for i in range(level_length):
                node , pos = queue.pop(0) #从队列中取出当前节点和位置
                if node.left:
                    queue.append((node.left,2*pos)) #左节点的位置是当前位置的两倍
                if node.right:
                    queue.append((node.right, 2*pos+1)) 

                #计算当前节点到最左节点的距离，用于更新最大宽度
                max_width=max(max_width,pos- left_pos+1)

        return max_width