-
Notifications
You must be signed in to change notification settings - Fork 0
/
662.hpp
72 lines (60 loc) · 1.86 KB
/
662.hpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
#ifndef LEETCODE_662_HPP
#define LEETCODE_662_HPP
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <numeric>
#include <stack>
#include <string>
#include "../common/leetcode.hpp"
using namespace std;
/*
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.
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode *root) {
if (root == nullptr)
return 0;
queue<int> count;
queue<TreeNode *> level;
level.push(root);
count.push(0);
int width = 1;
while (!level.empty()) {
auto size = level.size();
int left = 0;
int right = 0;
for (int i = 0; i < size; ++i) {
auto node = level.front();
int index = count.front();
level.pop();
count.pop();
if (i == 0)
left = index;
if (i == size - 1)
right = index;
if (node->left != nullptr) {
level.push(node->left);
count.push(index * 2);
}
if (node->right != nullptr) {
level.push(node->right);
count.push(index * 2 + 1);
}
}
width = max(width, right - left + 1);
}
return width;
}
};
#endif //LEETCODE_662_HPP