刷题 广度优先搜索（bfs）

文章目录1.二叉树的层次遍历1.二叉树的层次遍历题目给定一个二叉树返回其节点值自底向上的层次遍历。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历思路此题需要熟悉二叉树的层次遍历对于常见的层次遍历是利用队列先进先出的特性进行实现的总的思路就是我们每遍历一个节点就把该节点的左孩子和右孩子放进队列顺序很重要然后遍历完这个节点之后就从队列中取出头节点取出的节点有可能是右边的同层节点也有可能是下一层的第一个节点然后直到遍历完成。以上就是层次遍历的思路。对于本题额外需要注意的是判断什么时候遍历完一层我们可以采取使用两个数记录当前层个数cur和上一层的个数last来判断什么时候完成遍历的。此算法强烈推荐大家记住面试常考。遍历每一层的所有结点值实际上是一种/** * 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:vectorvectorintlevelOrderBottom(TreeNode*root){//队列求解if(rootnullptr)return{};queueTreeNode*que;vectorvectorintres;intlast1;//第一层个数为1que.push(root);while(!que.empty()){vectorintvec;intcur0;while(last--){TreeNode*nodeque.front();que.pop();//将队头元素弹出并放入当前层的结果vec中vec.push_back(node-val);if(node-left!nullptr){que.push(node-left);cur;//左节点不为空压入队列且个数加一}if(node-right!nullptr){que.push(node-right);cur;}}lastcur;res.push_back(vec);}reverse(res.begin(),res.end());returnres;}};