题解 | #二叉树的最大宽度#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    int res = 0;
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        if(root==nullptr) {
            return 0;
        }else{
            root->val=1;//特殊处理防止root节点val值不为1后续出现错误
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            TreeNode *start=q.front();//此层最左
            TreeNode *end=q.back();//此层最右
            for (int i = 0; i < size; i++) {
                TreeNode* cur = q.front();
                q.pop();//层序遍历，将节点值修改为其对应下标
                if (cur->left) {
                    q.push(cur->left);
                    cur->left->val = 2 * cur->val;
                }
                if (cur->right) {
                    q.push(cur->right);
                    cur->right->val = 2 * cur->val+1;
                }
            }
            res=max(res,end->val-start->val+1);//此层遍历完毕后，计算最大值(最左减去最右)
        }
        
        return  res;
    }
};