662. Maximum Width of Binary Tre

给定二叉树，求二叉树的最大宽度。二叉树某层的宽度是指其最左非空节点与最右非空节点之间的跨度。

解题思路：
二叉树层次遍历

对二叉树节点进行标号，根节点标号为1；若某节点标号为c，则其左右孩子标号分别为2c, 2c + 1

某层的宽度即为最右、最左节点标号之差+1

/**
 * 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 == NULL ) return 0;
    queue< TreeNode*  > qu;
    map< TreeNode*, int > mp;

    qu.push( root );
    int maxW = 0xc0c0c0c0;

    int numL = -1, numR = -1;

    while( !qu.empty() )
    {
        int n = qu.size();

        for( int i = 0; i < n; i++ )
        {
            TreeNode* tmp = qu.front();
            qu.pop();
            if( i == 0 )
            {
                numL = mp[tmp];
            }
            if( i == n-1 )
            {
                numR = mp[tmp];
            }

            if( tmp->left != NULL )
            {
                qu.push( tmp->left );
                mp[tmp->left] = mp[tmp] * 2;
            }
            if( tmp->right != NULL )
            {
                qu.push( tmp->right );
                mp[tmp->right] = mp[tmp] * 2 + 1;
            }
        }
        maxW = max( maxW, numR - numL + 1 );
    }
    return maxW;
}
};