662. Maximum Width of Binary Tree

二叉树同层两元素间距的计算

记二叉树的节点值为val，定义其左子节点的值为（如果存在），右子节点的值为（如果存在），则同层两节点的间距为（本题包括了两节点间的空节点，若不考虑空节点，用队算一下间隔就行）。

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int res = 1;
        root->val=1;
        while(!que.empty()){
            int n = que.size();
            int left_most = que.front()->val;
            while(n--){
                auto head = que.front();
                que.pop();
                res = max(res, head->val-left_most+1);
                if(head->left){
                    head->left->val=(2*head->val)%INT_MAX;
                    que.push(head->left);
                }  
                if(head->right){
                    head->right->val=(2*head->val+1)%INT_MAX;
                    que.push(head->right);
                } 
            }
        }
        return res;
    }
};