https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

我的方法一：队列

这个问题一看就是二叉树的广度优先遍历，用队列可以很简单实现BFS。
但是队列的遍历会失去层级的信息，如何保存层级信息。
可以再加入一个队列，这个队列保存当前节点的层级。

步骤

1. node_queue存放节点，level_queue存放层级信息
2. 现将根节点放入node_queue，层级0放入level_queue；
3. 然后开始遍历
   3.1 node_queue和level_queue pop一个节点，将该节点的值加入到结果vector<vector<int>>中，当然具体加入那一层，根据level_queue pop的值
   3.2 将该节点的左节点和右节点push到node_queue，层级+1后，push到level_queue中
4. 当node_queue为空时，说明节点已经遍历完

初始条件

1. node_queue，先push根节点

边界条件

1. 当跟节点为null时，直接返回
2. 当node_queue为空时，遍历结束
3. 只有当子节点不为空时，才会push到node_queue

复杂度

时间复杂度：O(N)，每个节点遍历了一次
空间复杂度：O(N)，最差需要N个长度的queue来存放信息

代码（一遍过）

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root){
            return ret;
        }

        queue<TreeNode*> node_queue;
        queue<int> level_queue;

        node_queue.push(root);
        level_queue.push(0);

        TreeNode* cur = 0;
        int level_cur = 0;

        while(!node_queue.empty()){
            cur = node_queue.front();
            node_queue.pop();
            level_cur = level_queue.front();
            level_queue.pop();

            if(cur->left){
                node_queue.push(cur->left);
                level_queue.push(level_cur+1);
            }

            if(cur->right){
                node_queue.push(cur->right);
                level_queue.push(level_cur+1);
            }

            if(ret.size() <= level_cur){
                vector<int> level_ret;
                level_ret.push_back(cur->val);
                ret.push_back(level_ret);
            }else{
                vector<int>& level_ret = ret[level_cur];
                level_ret.push_back(cur->val);
            }
        }

        return ret;
    }
};

其他人的方法

官方解法-不用level_queue

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/

主要思路

使用两层循环，第一层循环遍历所有的节点，第二层循环遍历某一层的节点。
所以第一层循环的迭代次数就是节点的层数，所以不需要level_queue来保存