Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
今天的题目相较于昨天,增加了一点难度,但不用慌,我们一起来看看吧.
还不熟悉的朋友们可以看看我的二叉树专题,相信你定能有所收获
题目: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专题Ⅱ】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
