Description

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:
Input:

       1
     /   \
    3     2
   / \     \  
  5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input:

      1
     /  
    3    
   / \       
  5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:

      1
     / \
    3   2 
   /        
  5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:

      1
     / \
    3   2
   /     \  
  5       9 
 /         \
6           7

Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note: Answer will in the range of 32-bit signed integer.

Explain

这道题的意思是：给一个有着满二叉树结构，但是有部分节点是null的树，然后求出这个树最宽的那一层的宽度。这个宽度就是每一层的最右和最左的距离的最大值。看起来不是很难做，有一个很暴力的方法就是把一层的节点都保存下来不管空不空，然后一个一个去遍历找到最左和最右的下标。但是我们作为一个coder，这么蠢的方法还是少用。这里要用到树的一个特点。每个节点的下标如果是i，那么它的左节点是 2 * i, 右节点是 2 * i + 1。然后，我们只要将每个节点和它的位置保存下来，做层序遍历。开始一层的遍历时，定义一个最左和一个最右的变量，将这层第一个节点的位置保存下来，然后每遍历这层的一个节点，将该节点的位置更新为最右变量的值。这一层遍历完后就可以得到这层的宽度，然后跟当前最大的宽度比较，然后更新最大值即可。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 0));
        int max = INT_MIN;
        while(!q.empty()) {
            int size = q.size();
            int start = 0;
            int end;
            for (int i = 0; i < size; i++) {
                auto cur = q.front();
                q.pop();
                if (i == 0) {
                    start = cur.second;
                }
                end = cur.second;
                if (cur.first->left) {
                    q.push(make_pair(cur.first->left, cur.second * 2));
                }
                if (cur.first->right) {
                    q.push(make_pair(cur.first->right, cur.second * 2 + 1));
                }
            }
            max = max > (end - start + 1) ? max : end - start + 1;
        }
        return max;
    }
};