69. 二叉树的层次遍历层次遍历+queue

给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问） 样例 给一棵二叉树 {3,9,20,#,#,15,7} ：

  3  / \ 9  20   /  \  15   7

返回他的分层遍历结果：

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

层次遍历+queue

参见数据结构与算法中写的，层次遍历是需要借助queue来做的，单纯的逐层遍历写起来是比较简单的，像这样要求不同的层还要放在不同的vector中，稍微难一点，我一开始也没想好到底怎么做，参考了别人的代码，实际上也不是很难，主要是记录一下每层的长度，那如何知道每一层的长度呢，用了一个很巧妙的方法。

1. 首先建立一个队列que，把根节点放进去。伪代码：

while（que非空） {         建立vector<int>   x;         int len=que.size();        while(len--)       {             把front->val放进x，并删掉front；             把front的左右子节点放入que；（先把front节点记录下来）                   }       把x放入vecto<vector<int>>  res ; }  返回  res；

这样操作的巧妙之处在于每次可以用len记录当前层的节点的个数，然后通过while循环把当前节点的下一层放进queue，这样while出来之后刚好是遍历完了这一层（而且已经删掉），queue里面剩下的就是下一层的节点了。

vector<vector<int>> levelOrder(TreeNode * root) {         vector<vector<int>>  res;         if(!root)         return res;                  queue<TreeNode*>   que;         que.push(root);         int len=1;      //第一个节点的大小                  while(!que.empty())         {             len=que.size();             vector<int> vtmp;                                       while(len--)             {                 TreeNode *tmp;                 tmp=que.front();                 vtmp.push_back(tmp->val);                 que.pop();                 if(tmp->left)   que.push(tmp->left);                 if(tmp->right)  que.push(tmp->right);                              }             if(!vtmp.empty())                 res.push_back(vtmp);         }         return res;                  // write your code here     }