二叉树——662. 二叉树最大宽度

题目：

思路：

层序遍历+辅助队列，但是还有些小细节，参考题解后（https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/cshuang-bai-de-yan-du-you-xian-you-hua-j-hqgb/）发现：

代码：

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (root == nullptr)
        {
            return 0;
        }

        // 保存最大的宽度
        int res = 0;

        // 队列用于广度优先遍历
        queue<TreeNode*> q;

        // 对于根节点的编号为0
        root->val = 0;
        q.push(root);

        while (!q.empty())
        {
            // 基于目前队列头和尾获得当前层的宽度
            res = max(res, q.back()->val - q.front()->val + 1);

            // 编号缩小的差值
            int offset = q.front()->val;

            // 遍历完当前层
            int n = q.size();
            for (int i = 0; i < n; ++i)
            {
                TreeNode* curr = q.front();
                q.pop();
                // 缩小数值
                curr->val -= offset;

                if (curr->left)
                {
                    // 转换为对应的编号
                    curr->left->val = curr->val*2;
                    q.push(curr->left);
                }
                if (curr->right)
                {
                    // 转换为对应的编号
                    curr->right->val = curr->val*2+1;
                    q.push(curr->right);
                }
            }
        }

        return res;
    }
};

作者：ffreturn
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/cshuang-bai-de-yan-du-you-xian-you-hua-j-hqgb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Rank：

Tips：

二叉树——662. 二叉树最大宽度

原文：https://www.cnblogs.com/lzyrookie/p/14701812.html