给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)
样例
给一棵二叉树 {3,9,20,#,#,15,7}
:
3
/ \
9 20
/ \
15 7
返回他的分层遍历结果:
[
[3],
[9,20],
[15,7]
]
层次遍历+queue
参见数据结构与算法中写的,层次遍历是需要借助queue来做的,单纯的逐层遍历写起来是比较简单的,像这样要求不同的层还要放在不同的vector中,稍微难一点,我一开始也没想好到底怎么做,参考了别人的代码,实际上也不是很难,主要是记录一下每层的长度,那如何知道每一层的长度呢,用了一个很巧妙的方法。
- 首先建立一个队列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
}