662. 二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例1:
输入:
示例二叉树
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
解题思路：
二叉树的常规解法也就BFS和DFS，我们要求二叉树的最大宽度，显然要用BFS。也就是一层一层地去找，直到最后一层，得出最大宽度（可能不在最后一层，具体例子可以看leetcode）。每一层都比较result=max(result, current_layer_breadth)。
常规解法：
def widthOfBinaryTree(root):
queue = collections.deque()
queue.append((root, 1))
res = 0
while queue:
# 当前层为首尾的差值加1
width = queue[-1][1] - queue[0][1] + 1
res = max(width, res)
for _ in range(len(queue)):
n, c = queue.popleft()
# 每一个子节点的序号都是它的父节点乘2，右节点再加1
if n.left: queue.append((n.left, c * 2))
if n.right: queue.append((n.right, c * 2 + 1))
return res
炫技解法：
def widthOfBinaryTree(root):
width = 0
level = [(1, root)]
while level:
width = max(width, level[-1][0] - level[0][0] + 1)
level = [kid for number, node in level
# 注意这里的enumerate用法
for kid in enumerate((node.left, node.right), 2 * number)
if kid]
return width
时间复杂度：O(N)
空间复杂度：O(N)
