Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
层序遍历，既可以用dfs实现也可以用bfs实现，用bfs实现的时候应该借助队列，代码如下：
dfs:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, );
return ret;
}
void dfs(TreeNode * root, int dep)
{
if(!root) return;
if(dep < ret.size()){
ret[dep].push_back(root->val);
}else{
vector<int> tmp;
tmp.push_back(root->val);
ret.push_back(tmp);
}
dfs(root->left, dep+);
dfs(root->right, dep+);
}
private:
vector<vector<int>> ret;
};bfs:
class Solution {
private:
struct Node{
TreeNode * treeNode;
int level;
Node(){}
Node(TreeNode * node, int lv)
:treeNode(node), level(lv){}
};
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<Node> nodeQueue;
vector<vector<int>> ret;
if(root == NULL)
return ret;
nodeQueue.push(Node(root, ));
int dep = -;
while(!nodeQueue.empty()){
Node node = nodeQueue.front();
if(node.treeNode->left)
nodeQueue.push(Node(node.treeNode->left, node.level + ));
if(node.treeNode->right)
nodeQueue.push(Node(node.treeNode->right, node.level + ));
if(dep == node.level)
ret[dep].push_back(node.treeNode->val);
else{
vector<int> tmp;
dep++;
ret.push_back(tmp);
ret[dep].push_back(node.treeNode->val);
}
nodeQueue.pop();
}
return ret;
}
};java版本的如下所示，同样的包括dfs以及bfs：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
dfs(ret, root);
return ret;
}
public void dfs(List<List<Integer>> ret, int dep, TreeNode root){
if(root == null)
return;
if(dep < ret.size()){
ret.get(i).add(root.val);
}else{
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(root.val);
ret.add(tmp);
}
dfs(ret, dep+1, root.left);
dfs(ret, dep+1, root.right);
}
}下面的是bfs，稍微麻烦一点，需要自己再创造一个数据结构，代码如下：
public class Solution {
public class Node{
int level;
TreeNode node;
Node(TreeNode n, int l){
level = l;
node = n;
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
int dep = -1;
List<List<Integer>> ret = new ArrayList<List<Integer>>();
Queue<Node> queue = new LinkedList<Node>();
queue.add(new Node(root, 0));
while(!queue.isEmpty()){
Node n = queue.poll();
if(n.node == null) continue;
if(dep < n.level){
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(n.node.val);
ret.add(tmp);
dep++;
}else{
ret.get(dep).add(n.node.val);
}
if(n.node.left != null) queue.add(new Node(n.node.left, n.level + 1));
if(n.node.right != null) queue.add(new Node(n.node.right, n.level + 1));
}
return ret;
}
}