题解 | #二叉树的最大宽度#
二叉树的最大宽度
https://www.nowcoder.com/practice/0975d62a307549cea32f353f354a7377
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
vector<vector<int>>res;
vector<int>tmp;
int widthOfBinaryTree(TreeNode* root) {
// write code here
if (root == NULL)return 0;
bfs(root);
int maxl = -1;
for (int i = 0; i < res.size(); i++) {
int j = 0, first = 0, last = 0, flag = 0;
while (j < res[i].size()) {
if (res[i][j] != -1 && flag == 0) {
flag = 1;
first = j;
last = j;
}
if (res[i][j] != -1 && flag == 1) {
last = j;
}
j++;
}
int len = last - first + 1;
maxl = max(maxl, len);
}
return maxl;
}
void bfs(TreeNode* root) {
if (root == NULL)return;
queue<TreeNode*>q;
q.push(root);
TreeNode* ocu = new TreeNode(-1);
int num = 0;
while (!q.empty()) {
int size = q.size();
if (num == size) {
return;
}
int len = 0, flag = 0;
while (size > 0) {
if (q.front()->left != NULL) {
q.push(q.front()->left);
} else {
q.push(ocu);
}
if (q.front()->right != NULL) {
q.push(q.front()->right);
} else {
q.push(ocu);
}
tmp.push_back(q.front()->val);
q.pop();
size--;
}
if (valid(tmp)) {
res.push_back(tmp);
tmp.clear();
} else {
return;
}
}
}
bool valid(vector<int> tmp) {
for (auto c : tmp) {
if (c != -1) {
return true;
}
}
return false;
}
};
投递杭州银行等公司7个岗位 >