102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
本题要求实现二叉树的层次遍历，居然没要求同时实现递归和迭代版本了，不过要求分层输出，还真是头一回见。
层次遍历不难，用队列+BFS实现，但是为了实现分层输出，我的方法是标记下一层的第一个节点，当队列走到下一层第一个节点时，说明该层结束，进入下一个循环。该版本的完整代码如下：
class Solution {
public: void bfs(vector < vector < int >> & ans, TreeNode * root) {
queue < TreeNode * > tree;
tree.push(root);
TreeNode * front;
while (!tree.empty()) {
vector < int > cand;
bool pushed = false;
TreeNode * next_level = NULL; // 下一层的第一个节点
front = tree.front();
while (!tree.empty() && front != next_level) {
tree.pop();
cand.push_back(front - > val);
if (front - > left != NULL) {
tree.push(front - > left);
if (!pushed) {
next_level = front - > left; // 标记
pushed = true; // 标记
}
}
if (front - > right != NULL) {
tree.push(front - > right);
if (!pushed) {
next_level = front - > right; // 标记
pushed = true; // 标记
}
}
if (tree.empty()) break;
front = tree.front();
}
ans.push_back(cand);
}
}
vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
bfs(ans, root);
return ans;
}
};本代码提交AC，用时9MS。
但是这个版本的代码看起来不够简洁，网上看题解发现递归迭代各一种简洁漂亮的解法。
我的解法不够简洁的原因是需要记录下一层第一个节点，然后判断当前层是否已遍历结束。但是仔细想想，这一层需要遍历的次数不就是这一层的节点数吗，而节点都存在队列中了，所以可以获取队列大小n，每层只循环n次即可。这个版本的代码如下，简洁了许多。
class Solution {
public: vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
queue < TreeNode * > tree;
tree.push(root);
TreeNode * f;
while (!tree.empty()) {
int n = tree.size();
vector < int > one_level;
for (int i = 0; i < n; i++) {
f = tree.front();
tree.pop();
one_level.push_back(f - > val);
if (f - > left != NULL) tree.push(f - > left);
if (f - > right != NULL) tree.push(f - > right);
}
ans.push_back(one_level);
}
return ans;
}
};本代码提交AC，用时6MS，也稍快了一点。
至于递归版本，我是没想到层次遍历也可以用递归来实现。递归的思路是，当当前遍历的层数和结果二维数组中的大小相等时，说明此时是第一次走到这一层，需要往二维数组中加一个空的一维数组，同时把这个节点的值加进去。然后依次先左后右的递归下去。
注意用递归实现层次遍历时，并不和我们肉眼层次遍历的顺序一致，它相当于DFS，只是把深搜的结果存到指定层的数组中了，最终输出的效果和普通的层次遍历一样。递归版本的代码如下：
class Solution {
public: void work(vector < vector < int >> & ans, int level, TreeNode * root) {
if (ans.size() == level) ans.push_back({}); // 重点
ans[level].push_back(root - > val);
if (root - > left != NULL) work(ans, level + 1, root - > left); // 先左
if (root - > right != NULL) work(ans, level + 1, root - > right); // 后右
}
vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
work(ans, 0, root);
return ans;
}
};本代码提交AC，用时6MS。
