cpp刷题打卡记录21——二叉树的层序遍历连招(102、107、199、637、429、515、116、117、104、111)

本篇是二叉树层序遍历的一套题都是以二叉树的层序遍历为基础的所以首先先来介绍二叉树的层序遍历。二叉树的层序遍历就是从左往右一层一层的来遍历二叉树借助队列的先进先出来进行实现。二叉树的层序遍历/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorvectorint levelOrder(TreeNode* root) { queueTreeNode* que; if(root ! NULL){ que.push(root); } vectorvectorint result; while(!que.empty()){ int size que.size(); vectorint v; for(int i 0; isize; i){ TreeNode* node que.front(); que.pop(); v.push_back(node-val); if(node-left){ que.push(node-left); } if(node-right){ que.push(node-right); } } result.push_back(v); } return result; } };思路就是一层一层进入队列同样也一层一层的出队列。内层的for循环是遍历每一层的节点。需要注意的是for循环的次数也就是size的大小每次的while存换size都会改变。图解过程理解好了二叉树的层序遍历我们就可以用它来解决很多题目。二叉树的层序遍历II就是把上一道题目二叉树的层序遍历最后得到的数组反转一下。二叉树的右视图就是在二叉树的层序遍历中将每一层最右边也就是每一层的最后面的的节点的值记录下来。二叉树的层平均值在层序遍历的时候计算每一层求和在求一个平均数。N叉树的层序遍历节点可能有多个孩子节点实际是一样的把判断左右孩子加入队列换成判断所以孩子加入队列。在每个树行中找最大值在层序遍历的过程中将每一层的最大值记录。填充每个节点的下一个右侧节点指针相对来说这道题有稍许稍许细节要注意。每个节点所处next指针需要赋值所以要知道每个节点的前一个节点是什么就容易写了。二叉树的最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。叶子节点是指没有孩子的节点。二叉树的最大深度其实也就是二叉树的层数所以只需层序遍历时记录其层数就可以了。二叉树的最小深度也可以用层序遍历来解决一旦找到没有孩子的节点就立马返回其当前层数就可以了。心得二叉树的层序遍历很重要是很多题目的基础并且初次自己写层序遍历并不容易完全写对要记住层序遍历的实现。