二叉树的层次遍历
给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)
样例
给一棵二叉树 {3,9,20,#,#,15,7} :
返回他的分层遍历结果:
[
[3],
[9,20],
[15,7]
]挑战
- 挑战1:只使用一个队列去实现它
- 挑战2:用DFS算法来做
标签
领英 脸书 二叉树遍历 队列 二叉树 宽度优先搜索优步
code
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public:
vector<vector<int>> levelOrder(TreeNode *root) {
// write your code here
vector<vector<int> > order;
queue<TreeNode*> queue;
int len;
if(root == NULL) {
return order;
}
queue.push(root);
len = queue.size();
while(!queue.empty()) {
vector<int> base;
len = queue.size();
while(len--) {
TreeNode *tmp=queue.front();
base.push_back(tmp->val);
queue.pop();
if(tmp->left)
queue.push(tmp->left);
if(tmp->right)
queue.push(tmp->right);
}
order.push_back(base);
}
return order;
}
};