662 Maximum Width of Binary Tree

662. Maximum Width of Binary Tree

1. Question

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 thenullnodes between the end-nodes are also counted into the length calculation.
Example 1:
1
Input:
2
3
4
1
5
/ \
6
3 2
7
/ \ \
8
5 3 9
9
10
11
Output:
12
4
13
14
Explanation:
15
The maximum width existing in the third level with the length 4 (5,3,null,9).
Copied!
Example 2:
1
Input:
2
3
4
1
5
/
6
3
7
/ \
8
5 3
9
10
11
Output:
12
2
13
14
Explanation:
15
The maximum width existing in the third level with the length 2 (5,3).
Copied!
Example 3:
1
Input:
2
3
4
1
5
/ \
6
3 2
7
/
8
5
9
10
11
Output:
12
2
13
14
Explanation:
15
The maximum width existing in the second level with the length 2 (3,2).
Copied!
Example 4:
1
Input:
2
3
1
4
/ \
5
3 2
6
/ \
7
5 9
8
/ \
9
6 7
10
11
Output:
12
8
13
14
Explanation:
15
The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Copied!
Note:Answer will in the range of 32-bit signed integer.

2. Implementation

(1) BFS
1
class Solution {
2
class NodeInfo {
3
TreeNode node;
4
int pos;
5
6
public NodeInfo(TreeNode node, int pos) {
7
this.node = node;
8
this.pos = pos;
9
}
10
}
11
public int widthOfBinaryTree(TreeNode root) {
12
if (root == null) {
13
return 0;
14
}
15
16
Queue<NodeInfo> queue = new LinkedList<>();
17
queue.add(new NodeInfo(root, 1));
18
19
int start = 0, end = 0, size = 0, maxWidth = 0;
20
21
while (!queue.isEmpty()) {
22
size = queue.size();
23
start = queue.peek().pos;
24
25
for (int i = 0; i < size; i++) {
26
NodeInfo curNodeInfo = queue.remove();
27
end = curNodeInfo.pos;
28
29
if (curNodeInfo.node.left != null) {
30
queue.add(new NodeInfo(curNodeInfo.node.left, 2 * end));
31
}
32
33
if (curNodeInfo.node.right != null) {
34
queue.add(new NodeInfo(curNodeInfo.node.right, 2 * end + 1));
35
}
36
}
37
maxWidth = Math.max(maxWidth, end - start + 1);
38
}
39
return maxWidth;
40
}
41
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(w)