[LeetCode] Problem 662 - Maximum Width of Binary Tree

Posted on | In ,

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example

No.1

Input: 

1
2
3
4
5
     1
   /   \
  3     2
 / \     \  
5   3     9

Output: 4

Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

No.2

Input: 

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
38
39
          1
         /  
        3    
       / \       
      5   3    
``` 

Output: 2

Explanation: The maximum width existing in the third level with the length 2 (5,3).

### No.3

Input: 

```bash
          1
         / \
        3   2 
       /        
      5   
```   

Output: 2

Explanation: The maximum width existing in the second level with the length 2 (3,2).

### No.4

Input: 

```bash
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7

Output: 8

Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note

Answer will in the range of 32-bit signed integer.

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
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
public int widthOfBinaryTree(TreeNode root) {
    if (root == null)
        return 0;

    int max = 0;
    LinkedList<TreeNode> queue = new LinkedList<>();
    root.val = 0;
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        max = Math.max(max, queue.peekLast().val - queue.peekFirst().val + 1);

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (node.left != null) {
                node.left.val = node.val * 2;
                queue.offer(node.left);
            }

            if (node.right != null) {
                node.right.val = node.val * 2 + 1;
                queue.offer(node.right);
            }
        }
    }

    return max;
}