662.二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

输入:

     1
   /   \
  3     2
 / \     \ 
5   3     9 

输出: 4

解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

1. 遍历一趟二叉树，把每个节点的线性表存储节点序号保存在节点val值上(合理利用资源)，用一个双端队列Deque实现层次遍历，记录每层第一个节点和最后一个节点的序号差，相减即为该层的宽度。