662-二叉树最大宽度

LeetCode 662. 二叉树最大宽度

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

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

示例 1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

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

method

层序遍历：满二叉树可以进行标号，根节点为1的话，左子树为根节点的pos*2，右子树为根节点的pos*2+1，这样我们就可以通过每层的最左边和最右边节点的pos算出这层的宽度

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, unsigned long long>> q;   // 会溢出
    q.push({root, 1});
    unsigned long long res = 0;
    while (!q.empty()) {
        int size = q.size();
        res = max(res, q.back().second - q.front().second + 1);
        for (int i = 0; i < size; i++) {
            auto [node, pos] = q.front();
            q.pop();
            if (node->left) q.push({node->left, pos * 2});
            if (node->right) q.push({node->right, pos * 2 + 1});
        }
    }
    return res;
}