문제
Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels.
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.
It is guaranteed that the answer will in the range of 32-bit signed integer
제한사항
- The given binary tree will have between 1 and 3000 nodes.
입출력 예
1
2
3
4
5
6
7
8
9
10
11
12
| Example 1:
Input:
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).
|
1
2
3
4
5
6
7
8
9
10
11
12
| Example 2:
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
|
1
2
3
4
5
6
7
8
9
10
11
12
| Example 3:
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Example 4:
Input:
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).
|
풀이
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) {
return 0;
}
// Tree의 level별 값이 있는 위치의 인덱스를 저장하는 map
std::map<int,std::vector<uint64_t>> m;
std::queue<std::pair<TreeNode*, std::pair<uint64_t, uint64_t>>> q;
q.push({root, {1, 1}});
// BFS
while (!q.empty()) {
auto item = q.front();
q.pop();
// 현재 node위치의 인덱스 계산하여 queue에 저장
// left node는 부모 node의 인덱스에 2*index,
// right node는 부모 node의 인덱스에 2*index + 1 이다
if (item.first->left) {
uint64_t index = item.second.second * 2;
m[item.second.first + 1].push_back(index);
q.push({item.first->left, {item.second.first + 1, index}});
}
if (item.first->right) {
uint64_t index = (item.second.second * 2) + 1;
m[item.second.first + 1].push_back(index);
q.push({item.first->right, {item.second.first + 1, index}});
}
}
int res = 1;
for (auto& level : m) {
if (level.second.size() < 2) {
continue;
}
int val = level.second.back() - level.second.front() + 1;
if (res < val) {
res = val;
}
}
return res;
}
};
|
