传送门：102. 二叉树的层序遍历
我们都知道，二叉树的层序遍历就是基于BFS算法进行的操作。而这题的层序遍历则要求我们需要以一层为单位输出到vector中。我们不妨在BFS过程中再用一层循环进行约束。使得每次循环队列中只有当前层的节点。因此队列中的数据量便是当前层节点的个数。当前层走完便跳出进入到下一层的循环之中。废话不多说，上代码。
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; //返回的vector if(!root) return ret; //空树直接返回 queue<TreeNode*> q; //定义队列 q.push(root); //根节点入队 while(q.size()) //BFS循环 { int len = q.size(); //当前层节点的个数 vector<int> v; //用于存储当前节点的vector for(int i = 0;i<len;i++) { TreeNode* t = q.front(); //获取队头节点 q.pop(); //出队 if(t->left) q.push(t->left); //子节点入队 if(t->right) q.push(t->right); v.push_back(t->val); //记录当前节点值 } ret.push_back(v); //记录当前层的vector } return ret; }
传送门：107. 二叉树的层序遍历 II
与上一题不一样，这题需要我们从最后一个节点开始向上遍历。虽然题目看着有点抽象，但实际上只需要我们将上一题得到的vector反转一下就能够得到正确答案。
vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> ret; if(!root) return ret; queue<TreeNode*> q; q.push(root); while(q.size()) { int len = q.size(); vector<int> v; for(int i = 0;i<len;i++) { TreeNode* t = q.front(); q.pop(); if(t->left) q.push(t->left); if(t->right) q.push(t->right); v.push_back(t->val); } ret.push_back(v); } reverse(ret.begin(),ret.end()); return ret; }
