1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 * memorize the most left position and most right position positions of the nodes at that level.
 * the position of left leaf is 2*position of root and the position of right left is 2*position + 1 of root.
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        int level = 1;
        int leftNum = 1;
        Deque<Tmp> q = new ArrayDeque<>();
        q.add(new Tmp(level, leftNum, root));
        
        while (!q.isEmpty()) {
            Tmp tmp = q.poll();
            if (tmp.level > level) {
                level = tmp.level;
                leftNum = tmp.num;
            }
            res = Math.max(res, tmp.num - leftNum + 1);
            if (tmp.node.left != null) q.add(new Tmp(tmp.level+1, 2*tmp.num, tmp.node.left));
            if (tmp.node.right != null) q.add(new Tmp(tmp.level+1, 2*tmp.num+1, tmp.node.right));
        }
        return res;
    }
    
    class Tmp {
        int level;
        int num;
        TreeNode node;
        public Tmp(int level, int num, TreeNode node) {
            this.level = level;
            this.num = num;
            this.node = node;
        }
    }
}