手撕LeetCode #662——Python

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)