为什么下面都说很简单……难道我真的很菜吗…………
好吧可能是数据结构忘了很多，层序遍历我记得老师是讲过的。
先搜了下层序遍历惯用的套路，就是不断储存下一级（left和right）的节点，同时不断遍历储存的节点，每次将节点值放进去。
这道题和普通层序遍历还是有差别的，需要将遍历结果按照不同层分开。
这就要求记录层数。
我最初的想法是，建立存储节点的容器的同时建立存储节点对应层数的容器，每次存储下一级的节点就顺势存储这一级的层数加一。
/**
* 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:
vector<int> l;
vector<TreeNode*> t;
vector<vector<int>> v;
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL) return v;
l.push_back(0);
t.push_back(root);
while(!l.empty()){
int layer=l[0];
TreeNode* tree=t[0];
l.erase(l.begin());
t.erase(t.begin());
if(v.size()<=layer) v.push_back(vector<int> ());
v[layer].push_back(tree->val);
if(tree->left){
l.push_back(layer+1);
t.push_back(tree->left);
}
if(tree->right){
l.push_back(layer+1);
t.push_back(tree->right);
}
}
return v;
}
};在评论区看到这样一种递归解法，感觉更通俗易懂一些，看了一遍自己写了一遍：
/**
* 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:
vector<vector<int>> result;
void dg(TreeNode* tree,int layer){
if(tree==NULL) return ;
if(result.size()<=layer) result.push_back(vector<int> ());
result[layer].push_back(tree->val);
if(tree->left) dg(tree->left,layer+1);
if(tree->right) dg(tree->right,layer+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
dg(root,0);
return result;
}
};