Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

题目:102. 二叉树的层序遍历

题解:

代码实现:

题目:2583. 二叉树中的第 K 大层和

题解:

代码实现:

题目:剑指 Offer II 044. 二叉树每层的最大值

题解:

代码实现:

完结撒花：

今天的题目相较于昨天,增加了一点难度,但不用慌,我们一起来看看吧.

还不熟悉的朋友们可以看看我的二叉树专题,相信你定能有所收获

题目:102. 二叉树的层序遍历

题解:

什么是层序遍历呢?相较于前中后序的遍历方式,层序遍历是一层层的去遍历,例如这一题

那如何做到一层层遍历呢?

可以先将一个节点放入队列,每当取出一个节点的时候就将其左右非空节点放入队列中.

如此循环往复,当队列为空的时候,此时就将二叉树层序遍历完了.

所以我们需要一个队列来存储树的节点,那么如何知道这一层遍历完了呢?

我们可以在取出每次开始取出节点的时候,记录下此时队列内的数据个数,此时就是该层的节点个数.(可以看看上图)

(注意队列是头先出,从尾插入)每次插入的是非空节点

代码实现:

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*>tree;vector<vector<int>>ans;if(root==NULL)return {};tree.push(root);int height=0;while(!tree.empty()){height=tree.size();ans.push_back(vector<int>());for(int i=1;i<=height;i++){TreeNode*tmp=tree.front();tree.pop();ans.back().push_back(tmp->val);if(tmp->left)tree.push(tmp->left);if(tmp->right)tree.push(tmp->right);}            }return ans;}
};

题目:2583. 二叉树中的第 K 大层和

题解:

在有了上一题的基础下,这题就十分的简单啦,整体思想如下:先将每一层的值相加,然后放入容器当中,最后排个序,取出k-1层的即可.

具体的来看:层序遍历每一层的值,当遍历完这一层的时候,也就是size==0时,将这层的结果放入容器当中,最后通过lambda表达式实现从大到小排序,返回k-1层的结果(下标从0开始)

代码实现:

class Solution {
public:long long kthLargestLevelSum(TreeNode* root, int k) {queue<TreeNode*>tag;vector<long long>res;tag.push(root);while(!tag.empty()){int size=tag.size();int ans=0;for(int i=1;i<=size;i++){TreeNode*tmp=tag.front();tag.pop();ans+=tmp->val;if(tmp->left)tag.push(tmp->left);if(tmp->right)tag.push(tmp->right);}res.push_back(ans);}sort(res.begin(),res.end(),[](auto const &c1,auto const &c2){return c1>=c2;});if(res.size()<k)return -1;else return res[k-1];}
};

题目:剑指 Offer II 044. 二叉树每层的最大值

题解:

这里有两种方法(深度优先搜索与广度优先搜索)其实也就是前序遍历与层序遍历,层序遍历这里简单提一下.与上面的大同小异就不过多赘述了:依旧是遍历出每一层最大的值,将其放入数组即可.

深度优先搜索:先看看基础情况若当前遍历到的值等于size,则说明这一层还没有元素被放入到容器当中,此时直接放入遍历到的元素即可,若反之,则取容器中对应层的元素与现在要放入的元素比较取最大值即可.

代码实现:

class Solution0 {//dfs
public:void preorder(TreeNode*root,vector<int>&res,int pi){if(pi==res.size()){res.push_back(root->val);}else{res[pi]=max(res[pi],root->val);}if(root->left){preorder(root,res,pi+1);}if(root->right){preorder(root, res,pi+1);}}vector<int> largestValues(TreeNode* root) {int i=0;if(!root)return {};vector<int>res;preorder(root,res,0);return res;}
};class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*>tree;vector<int>ans;if(root==NULL)return {};tree.push(root);int height=0;while(!tree.empty()){int Max=INT_MIN;height=tree.size(); for(int i=1;i<=height;i++){TreeNode*tmp=tree.front();tree.pop();Max=max(Max,tmp->val);if(tmp->left)tree.push(tmp->left);if(tmp->right)tree.push(tmp->right);}ans.push_back(Max);}return ans;}
};