662.二叉树最大宽度

【LetMeFly】662.二叉树最大宽度：一组奇怪的数据

力扣题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

方法一：层次遍历

层序遍历二叉树，在遍历的同时，二叉树的“坐标”同时入队。

在处理每一层时，更新最左和最右的坐标。

处理完这一层后，$最右 - 最左 + 1$就是这层的宽度。

处理一个节点时，若此节点具有左子节点，那么左子节点的编号为这个节点编号的二倍

若具有右子节点，那么右子节点的编号是这个节点编号的二倍+1

具体原因为：

• 时间复杂度$O(n)$，其中$n$为二叉树节点个数
• 空间复杂度$O(n)$

提交我下面的代码并不能通过这道题，因为这道题数据有一组似乎得手写高精度。官方题解也溢出了（截止至20220827 15:03）。

已反馈至Github:https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/8816

至发文为止不能AC的代码

C++

typedef unsigned long long ull;
// typedef __int128 ull;
typedef pair<TreeNode*, ull> pii;
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        ull ans = 0;
        queue<pii> q;
        q.push({root, 1});
        ull lastL, lastR;
        // int cntDebug = 0;
        while (q.size()) {
            
            // cntDebug++;
            // if (cntDebug > 1750) {
            //     printf("q.size() = %lld, q:[");
            //     // queue<pii> q2, q3 = q;
            //     // while (q3.size()) {
            //     //     q2.push(q3.front());
            //     //     q3.pop();
            //     // }
            //     // while (q2.size()) {
            //     //     cout << q2.front().first->val << ", ";
            //     // }
            // }
            ull mostL = q.front().second, mostR = mostL;
            for (int i = q.size(); i > 0; i--) {
                auto[node, loc] = q.front();
                // printf("loc = %llu\n", loc);
                // if (node->val) {
                //     printf("node->val = %d, loc = %llu\n", node->val, loc);
                // }
                q.pop();
                mostL = min(mostL, loc);
                mostR = max(mostR, loc);
                if (node->left) {
                    q.push({node->left, loc * 2 - 1});
                }
                if (node->right) {
                    q.push({node->right, loc * 2});
                }
            }
            lastL = mostL, lastR = mostR;
            ans = max(ans, mostR - mostL + 1);
            // if (cntDebug > 1750) {
            //     // cout << "mostL = " << lastL << ", mostR = " << lastR << endl;
            //     printf("mostL = %llu, mostR = %llu\n", mostL, mostR, q.size());
            // }
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126558271