We can go through the tree in level order and mark each node with an integer standing for its position.

When we finish a level, we calculate the End - Begin integer which stands for the maximum width.

BUT i have to modify the node's val

```
public int widthOfBinaryTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
root.val = 1;
queue.offer(root);
int max = 0;
while (!queue.isEmpty()) {
int l = queue.size();
int begin = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
for (int i = 0; i < l; i++) {
TreeNode node = queue.poll();
begin = Math.min(begin, node.val);
end = Math.max(end, node.val);
if (node.left != null) {
node.left.val = (node.val << 1) - 1;
queue.offer(node.left);
}
if (node.right != null) {
node.right.val = node.val << 1;
queue.offer(node.right);
}
}
max = Math.max(max, end - begin + 1);
}
return max;
}
```