<commit_before><commit_msg>Maximum Width of Binary Tree<commit_after>/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
struct Item {
    TreeNode* root;
    int64_t level;
    int64_t pos;
};
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        std::queue<Item> q;
        q.emplace(Item{root, 0, 1});
        int64_t curlevel = 0, curpos = 1, ret = 0, MOD = 2147483649;
        while (!q.empty()) {
            auto item = q.front();
            q.pop();
            if (item.level != curlevel) {
                curlevel = item.level;
                curpos = item.pos;
            } else {
                ret = std::max(ret, item.pos - curpos + 1);
            }
            if (item.root->left)
                q.emplace(Item{item.root->left, item.level+1, item.pos*2 % MOD});
            if (item.root->right)
                q.emplace(Item{item.root->right, item.level+1, (item.pos*2+1) % MOD});
        }
        return ret;
    }
};
{'fraction_non_alphanumeric': 0.15449654112221367, 'fraction_numerical': 0.022290545734050732, 'mean_word_length': 1.9258426966292135, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1712473', 'n_tokens_mistral': 451, 'n_tokens_neox': 430, 'n_words': 102}