问题给定一棵二叉树，编写一个函数来获取树的最大宽度。树的宽度是所有层中最大的宽度。此二叉树与满二叉树具有相同的结构，但有些节点是空的。每层的宽度定义为两个端点之间的长度（该层最左边和最右边的非空节点，两个端点之间的空节点也包含在长度中）。示例1：输入：1/\32/\\539输出：4解释：最大值出现在宽度为4(5,3,null,9)的树的第3层。示例2：输入：1/3/\53输出：2解释：最大值出现在宽度为2(5,3)的树的第3层。示例3：输入：1/\32/5输出：2解释：最大值出现在宽度为2(3,2)的树的第2层。示例4：输入：1/\32/\59/\67输出：8解释：最大值出现在树的第4层，宽度为8(6,null,null,null,null,空，空，7）。注意：答案在32位有符号整数的表示范围内。BFS满二叉树的特点：节点p的左子节点序号为2p，右子节点序号为2p+1。在同一层中，第一个元素和最后一个元素的坐标差就是最大宽度。CodePython3#定义二叉树节点。#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclass解决方案：defwidthOfBinaryTree(self,root:TreeNode)->int:ifnotroot:return0#坐标和节点分别queue=[(0,root)]res=1#BFSwhilequeue:#第一个和最后一个元素的坐标区别在于最大宽度res=max(res,queue[-1][0]-queue[0][0]+1)tmp=[]fori,qinqueue:ifq.left:tmp.append((i*2,q.left))ifq.right:tmp.append((i*2+1,q.right))queue=tmpreturnres链接GitHub
