Maximum Width of Binary Tree LeetCode solution in C++

1
/*
2
Run BFS and store the index of the node when it was stored in the flattened
3
manner. Take the diff of each of the level and keep traking of max value
4

5
 */
6
class Solution {
7
 public:
8
  int widthOfBinaryTree(TreeNode *root) {
9
    if (!root) return 0;
10
    int res = 0;
11
    queue<pair<TreeNode *, int>> q;
12
    q.push({root, 0});
13
    while (!q.empty()) {
14
      int n = q.size();
15
      res = max(res, q.back().second - q.front().second + 1);
16
      int start = q.front().second;
17
      while (n--) {
18
        TreeNode *p = q.front().first;
19
        long long ind = q.front().second - start;
20
        q.pop();
21
        if (p->left) q.push({p->left, ind * 2 + 1});
22
        if (p->right) q.push({p->right, ind * 2 + 2});
23
      }
24
    }
25
    return res;
26
  }
27
};