102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7],

  1. 3
  2. / \
  3. 9  20
  4. /  \
  5. 15   7

返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

解题思路

本题和第二周的 429. N叉树的层序遍历 其实几乎是同一个题，二叉树的层次遍历只是N叉树层序遍历的一种特殊情况。除了需要层次遍历以外，本题还要求打印出每层所包含的结点。普通的层序遍历每次从队列中取出一个结点，并将其踢出队列，然后将该结点的所有子结点push到队列中。
如果简单模拟下这个过程：

     3
  /    \
  9     20
 / \    / \
6   8  15  7

一开始将root结点3入队 | 3所在层数为1，操作完后队列中元素个数为1个 [ 3 ]
取出队首元素3，将其子结点9和20入队 | 9和20所在层数为2，操作完后队列中元素个数为2个 [ 9 20]
取出队首元素9，将其子结点 6和 8 入队 | 6和8所在层数为3，操作完后队列中元素个数为3个 [ 20 6 8 ]
取出队首元素20，将其子结点 15和 7 入队 | 15和7所在层数为3，操作完后队列中元素个数为4个 [ 6 8 15 7 ]
………………..
当遍历9和20时，9和20是同一层的结点，其实是要分别取出它们，并把它们的孩子结点push到队列中的，而它们的孩子结点其实是同一层的，所以我们可以在不断从队列中[取结点push子结点]这个操作之前控制这部分结点是同层结点。怎么知道哪些是同层结点呢，在上面的例子中，在操作完[取队首3，push孩子9和20]后，队列的个数变为2个，而它们两个就是同层结点，我们记录此时队列的大小，即是这层的结点个数，循环遍历每个结点把它们的孩子push到队列中，而两个结点都操作完之后此时队列结点个数为4，是第三层。记录此时队列数，重复上面的操作………..
每层我们所记录的队列中结点个数（同层个数），其实就是来源于上一层所有结点作完操作之后队列里面的结点个数，具体看如下核心代码

  while(!que.empty()){
      vector<int> layer;//记录同层结点
      /*que.size()来自上一层结点把所有子结点入队后的结点个数 */
      for(int i=que.size();0<i;i--){
          TreeNode* top = que.front();
          que.pop();//去掉当层此结点
          if(top->left != NULL)
          que.push(top->left);//入下层左孩子
          if(top->right != NULL)
          que.push(top->right);//下层右孩子
          layer.push_back(top->val);
      }
      res.push_back(layer);
 }

完整代码实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        if(root != NULL)
            que.push(root);
        while(!que.empty()){
            vector<int> layer;
        /*此处不可以为 for(int i=0;i<que.size();i++) 
        因为这样que.size()会随着上次循环的push操作而动态变化*/
            for(int i=que.size();0<i;i--){
                TreeNode* top = que.front();
                que.pop();
                if(top->left != NULL)
                    que.push(top->left);
                if(top->right != NULL)
                    que.push(top->right);
                layer.push_back(top->val);
            }
            res.push_back(layer);
        }
        return res;
    }
};