题目：
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节
点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
Related Topics 树
👍 227 👎 0
leetcode submit region begin(Prohibit modification and deletion)
Definition for a binary tree node.
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
leetcode submit region end(Prohibit modification and deletion)
AC解答详情如下：不会的就没办法了 ，事实上你就必须会
Definition for a binary tree node.
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
if not root: return 0
queue = [(0,root)] #记录索引和值
res = 1 #默认只有root时宽度为1
while queue:
res = max(res,queue[-1][0] - queue[0][0] +1)
# 每一层最左边的索引位置 和最右边的索引位置之差就是当前层宽度，取MAX就是最大宽度
tmp =[]
for i,q in queue:
if q.left:
tmp.append((i2,q.left)) #满二叉树的索引位置
if q.right:
tmp.append((i2 +1,q.right))
queue =tmp
return res
作者：vigilant-7amportprg
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/zui-jian-dan-zui-rong-yi-li-jie-de-ceng-w4h7m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
