1.题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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位有符号整数的表示范围内。

2.解题思路

对二叉树进行层次遍历，每层去除头部空节点和尾部空节点，剩下的节点个数即为每层的宽度

注意对空节点的处理，如果当前节点的左孩子或者右孩子为空，与普通层次遍历不同，也要把它们加入队列中，并且如果出队的空节点，要手动把两个空节点作为它的孩子节点加入到队列中

3.代码实现

使用python中的deque实现队列，否则使用list会超时

from collections import deque class Solution(object): def widthOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ maxsize=0 d = deque() d.append(root) while d: while d and d[0]==None: d.popleft() while d and d[-1]==None: d.pop() size=len(d) maxsize=max(size,maxsize) for i in range (size): t=d.popleft() if t==None: d.append(None) d.append(None) continue d.append(t.left) d.append(t.right) return maxsize