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。