Leetcode 662. Maximum Width of Binary Tree

 这道题和314 Binary Tree Vertical Order Traversal类似，区别就是纵坐标的计算不同，这道题不存在有多个节点重合到一个纵坐标的情况。如果某个节点的位置是X，那么它的左子节点应该是2X,右子节点位置是2X+1

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution {

public:

    int widthOfBinaryTree(TreeNode* root) {

        if(root==nullptr) return 0;

        queue<pair<TreeNode*,long long int>> q;

        q.push(make_pair(root,0));

        long long int minCol=0;

        long long int maxCol=0;

        int maxWidth=1;

        while(q.size()>0){

            int size = q.size();

            for(int i=0; i<size; i++){

                pair<TreeNode*,int> cur = q.front();

                q.pop();

                TreeNode* node = cur.first;

                long long int col = cur.second;

                if(i==0){

                    minCol = col;

                }

                if(i==size-1){

                    maxCol = col;

                    maxWidth = max(maxWidth, maxCol-minCol+1);

                }

                if(node->left != nullptr){

                    q.push({node->left, col*2});

                }

                if(node->right != nullptr){

                    q.push({node->right, col*2+1});

                }

            }

        }

        return maxWidth;

    }

};