二叉树的层序遍历习题集锦

啊，鬼知道我这一周到底干了啥；干啥啥不行，吃饭第一名，冬天快要来了，有羽绒服不需要脂肪来御寒，请有点自知之明，微笑脸。要把前几天没做的给补回来 这次就来个二叉树的二层次遍历叭，从二叉树的层次遍历可以延伸出好多题目

1.102. 二叉树的层序遍历 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode *> q;//层次遍历利用队列 vector<vector<int> > res;//返回的最后结果 if(root){ q.push(root);//先将根节点加入队列中 while(!q.empty()){//只要队列不空 vector<int> path;//用来保存每一层的遍历顺序 int size=q.size(); for(int i=0;i<size;i++){ TreeNode *t=q.front(); q.pop(); path.push_back(t->val); if(t->left) q.push(t->left);//左孩子不为空，将左孩子加入队列中 if(t->right) q.push(t->right);//右孩子不空，将右孩子加入队列中 } res.push_back(path);//每一层的遍历结果存起来 } } return res; } };

2、429. N叉树的层序遍历 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int> >res; queue<Node *> q; if(root) q.push(root); while(!q.empty()){ int size=q.size(); vector<int> path; for(int i=0;i<size;i++){ Node *t=q.front(); q.pop(); path.push_back(t->val); for(auto it:t->children){//N叉树的层次遍历只是在这里稍稍有点不同，二叉树只有两个节点，不需要用个for循环就可以对它的孩子进行判断，并决定到底要不要加入队列中 if(it) q.push(it);//只要孩子结点不空，就加入队列中 } } res.push_back(path); } return res; } };

3、107. 二叉树的层次遍历 II 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如： 给定二叉树 [3,9,20,null,null,15,7], 这个和第一题相比就是个水题，哈哈哈，我又在欺骗自己多看了一道题。 就是在层次遍历的基础上，进行reverse就行了，其他都不需要变

4、637. 二叉树的层平均值 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 这次就不需要保存每层的路径了，只要计算每层的和，再除以每层的个数（就是当前队列的长度，应为一层遍历结束之后，如果队列不空，队列中保存的就是下一层的结点个数）

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> res; queue<TreeNode *> q; if(root){ q.push(root); while(!q.empty()){ double sum=0; int size=q.size(); for(int i=0;i<size;i++){ TreeNode *t = q.front(); q.pop(); sum+=t->val; if(t->left){ q.push(t->left); } if(t->right){ q.push(t->right); } } res.push_back(sum/size); } } return res; } };

5、199. 二叉树的右视图 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 说白了，就是将每层最右边结点的值输出来就行了，只需要在循环里判断当前队列中是不是最后一个结点，代码还是第一题的那个代码，加一句话

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode *> q; vector<int> res; if(root){ q.push(root); while(!q.empty()){ // vector<int> path; int size=q.size(); for(int i=0;i<size;i++){ TreeNode *t=q.front(); q.pop(); //path.push_back(t->val); if(i==size-1) res.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } //res.push_back(path); } } return res; } };

---------坑位、逐渐填满------------------------------------------- 6、2020-10-27 链接地址链接：https://leetcode-cn.com/problems/cousins-in-binary-tree 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。 思路：还是层次遍历的模板，判断两个节点是否在同一层，注意一点就是如果是在同一层而且父亲节点相同的话仍然不满足条件，前几次WA一直在载在这里了

/** * 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: bool isCousins(TreeNode* root, int x, int y) { queue<TreeNode *> q;//层次遍历利用队列 // vector<vector<int> > res;//返回的最后结果 int flag=0,first_father,second_father; if(root){ if(root->val == x || root->val==y) return false;//根节点这里只有一个结点，他没有堂兄弟 q.push(root);//先将根节点加入队列中 while(!q.empty()){//只要队列不空 vector<int> path;//用来保存每一层的遍历顺序 int size=q.size(); for(int i=0;i<size;i++){ TreeNode *t=q.front(); q.pop(); path.push_back(t->val); if(t->left) { q.push(t->left);//左孩子不为空，将左孩子加入队列中 if(t->left->val==x || t->left->val == y){ //如果左孩子等于其中一个目标值，flag++，并且记录它的爸爸 flag++; first_father=t->val; } } if(t->right) { q.push(t->right);//右孩子不空，将右孩子加入队列中 if(t->right->val==x || t->right->val ==y){//和左孩子同理 flag++; second_father=t->val; } } } // 这里是处理每一层的地方 if(flag==1) return false;//如果flag=1，说明该层只有一个结点等于目标结点值，情况就类似于题目中给的例子 if(flag==2 && first_father==second_father) return false;//如果两个待判断结点为于同一层，判断它们的爸爸相等不，如果相等，直接返回false if(flag==2 && first_father!=second_father) return true;//出现在同一层且他们的爸爸不同，返回在true } } return false; } };

-------2020.11.02---------- 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 思路：我今天发现我只有用自己的电脑敲代码才行云流水，在学校机房做的时候，我的天，脑子里啥也不记得，层次遍历的模板都忘记了。回到实验室用自己的电脑一遍AC，我也简直了。道题就是在层次遍历的基础上加上判断，偶数层的path要进行反转，再存进去

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int> > res; if(!root) return res; queue<TreeNode *> q; q.push(root); int count=0; while(!q.empty()){ vector<int> path; int size=q.size(); for(int i=0;i<size;i++){ TreeNode *node = q.front(); q.pop(); path.push_back(node->val); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } count++; if(count%2==0) reverse(path.begin(),path.end());//偶数层需要进行反转 res.push_back(path); } return res; } };