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

---

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
算法思想：
迭代的方法，采用层序遍历，注意这里使用了队列queue来辅助运算，queue里存的是一个pair，包括结点和其当前位置。在进入新一层的循环时，首先将首结点的位置保存出来当作最左位置，然后对于遍历到的结点，都更新右结点的位置，遍历一层的结点后来计算宽度更新结果res。
*/
//算法实现：

class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root)
return 0;
int res = 0;
queue> q; //包括结点和其当前位置的队列类型
q.push({root, 1});
while (!q.empty()) {
int begin = q.front().second, end = 0, n = q.size(); //每层首结点位置，尾结点位置，结点个数
for (int i = 0; i < n; ++i) { //遍历一层 TreeNode* t = q.front().first; //当前结点 end = q.front().second; //当前结点位置 q.pop(); if (t->left) //如果左子树存在，end*2
q.push({t->left, end * 2});
if (t->right) //如果右子树存在，end*2+1
q.push({t->right, end * 2 + 1});
}
res = max(res, end - begin + 1); //求每层的宽度最大值
}
return res;
}
};