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     }