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;}
};
完结撒花:
🌈本篇博客的内容【你真的会二叉树了嘛? --二叉树LeetCode专题Ⅱ】已经结束。
🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。
🌈诸君,山顶见!