第一題107. 二叉樹的層序周遊 II
題目連結
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
簡單題要争取一遍ac。
重點在reverse(res.begin(), res.end())
要記得學會用reverse。
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if(root == nullptr) return res;
que.push(root);
while(!que.empty()){
int n = que.size();
vector<int> v;
while(n--){
TreeNode* temp = que.front();
v.push_back(temp->val);
if(temp->left != nullptr) que.push(temp->left);
if(temp->right != nullptr) que.push(temp->right);
que.pop();
}
res.push_back(v);
}
reverse(res.begin(), res.end());
return res;
}
};
第二題199. 二叉樹的右視圖
題目連結
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/binary-tree-right-side-view/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q;
vector<int> res;
if(root == nullptr) return res;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i = 1; i <= n; i++){
TreeNode* temp = q.front();
if(temp->left != nullptr) q.push(temp->left);
if(temp->right != nullptr) q.push(temp->right);
if(i == n){
res.push_back(temp->val);
}
q.pop();
}
}
return res;
}
};
第三題637. 二叉樹的層平均值
題目連結
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
坑很多 一定要注意再注意
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> q;
vector<double> res;//注意double
if(root != nullptr) q.push(root);
while(!q.empty()){
int n = q.size();
//注意:節點值的範圍在32位有符号整數範圍内。用double
double sum = 0;//直接求目前這一層的和,不用vector
for(int i = 0; i < n; i++){
TreeNode *temp = q.front();
sum += temp->val;
if(temp->left != nullptr) q.push(temp->left);
if(temp->right != nullptr) q.push(temp->right);
q.pop();
}
res.push_back(sum / n);//注意要用n的值,是以中途n不能改變
}
return res;
}
};
第四題429. N 叉樹的層序周遊
題目連結
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/submissions/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> que;
if(root != nullptr) que.push(root);
while(!que.empty()){
int n = que.size();
vector<int> v;
while(n--){
Node* temp = que.front();
v.push_back(temp->val);
que.pop();
for(int i = 0; i < temp->children.size(); i++){
que.push(temp->children[i]);
}
}
res.push_back(v);
}
return res;
}
};
第五題515. 在每個樹行中找最大值
題目連結
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/submissions/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que;
vector<int> res;
if(root != nullptr) que.push(root);
while(!que.empty()){
int n = que.size();
int max = INT_MIN;
while(n--){
TreeNode* temp = que.front();
que.pop();
max = max > temp->val ? max : temp->val;
if(temp->left != nullptr) que.push(temp->left);
if(temp->right != nullptr) que.push(temp->right);
}
res.push_back(max);
}
return res;
}
};
第六題116. 填充每個節點的下一個右側節點指針/117. 填充每個節點的下一個右側節點指針 II
題目連結
來源:力扣(LeetCode)
連結:
116:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/submissions/
117:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題目描述
題目分析
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if(root != nullptr) que.push(root);
while(!que.empty()){
int n = que.size();
for(int i = 1;i <= n; i++){
Node* temp = que.front();
que.pop();
if(i < n){
temp->next = que.front();
}else if(i == n){
temp->next = nullptr;
}
if(temp->left != nullptr) que.push(temp->left);
if(temp->right != nullptr) que.push(temp->right);
}
}
return root;
}
};