LeetCode OJ：Binary Tree Level Order Traversal（二叉树的层序遍历）

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},

return its level order traversal as:

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

层序遍历，既可以用dfs实现也可以用bfs实现，用bfs实现的时候应该借助队列，代码如下：

dfs:

 1 class Solution {
 2 public:
 3     vector<vector<int>> levelOrder(TreeNode* root) {
 4         dfs(root, 0);
 5         return ret;
 6     }
 7     void dfs(TreeNode * root, int dep)
 8     {
 9         if(!root) return;
10         if(dep < ret.size()){
11             ret[dep].push_back(root->val);
12         }else{
13             vector<int> tmp;
14             tmp.push_back(root->val);
15             ret.push_back(tmp);
16         }
17         dfs(root->left, dep+1);
18         dfs(root->right, dep+1);
19     }
20 private:
21     vector<vector<int>> ret;
22 };

bfs:

 1 class Solution {
 2 private:
 3     struct Node{
 4         TreeNode * treeNode;
 5         int level;
 6         Node(){}
 7         Node(TreeNode * node, int lv)
 8         :treeNode(node), level(lv){}
 9     };
10 public:
11     vector<vector<int>> levelOrder(TreeNode* root) {
12         queue<Node> nodeQueue;
13         vector<vector<int>> ret;
14         if(root == NULL)
15             return ret;
16         nodeQueue.push(Node(root, 0));
17         int dep = -1;
18         while(!nodeQueue.empty()){
19             Node node = nodeQueue.front();
20             if(node.treeNode->left)
21                 nodeQueue.push(Node(node.treeNode->left, node.level + 1));
22             if(node.treeNode->right)
23                 nodeQueue.push(Node(node.treeNode->right, node.level + 1));
24             if(dep == node.level)
25                 ret[dep].push_back(node.treeNode->val);
26             else{
27                 vector<int> tmp;
28                 dep++;
29                 ret.push_back(tmp);
30                 ret[dep].push_back(node.treeNode->val);
31             }
32             nodeQueue.pop();
33         }
34         return ret;
35     }
36 };

java版本的如下所示，同样的包括dfs以及bfs：

 1 public class Solution {
 2     public List<List<Integer>> levelOrder(TreeNode root) {
 3         List<List<Integer>> ret = new ArrayList<List<Integer>>();
 4         dfs(ret, root);
 5         return ret;
 6     }
 7     
 8     public void dfs(List<List<Integer>> ret, int dep, TreeNode root){
 9         if(root == null)
10             return;
11         if(dep < ret.size()){
12             ret.get(i).add(root.val);
13         }else{
14             List<Integer> tmp = new ArrayList<Integer>();
15             tmp.add(root.val);
16             ret.add(tmp);
17         } 
18         dfs(ret, dep+1, root.left);
19         dfs(ret, dep+1, root.right);
20     }
21 }

下面的是bfs，稍微麻烦一点，需要自己再创造一个数据结构，代码如下：

 1 public class Solution {
 2     public class Node{
 3         int level;
 4         TreeNode node;
 5         Node(TreeNode n, int l){
 6             level = l;
 7             node = n;
 8         }
 9     }
10     public List<List<Integer>> levelOrder(TreeNode root) {
11         int dep = -1;
12         List<List<Integer>> ret = new ArrayList<List<Integer>>();
13         Queue<Node> queue = new LinkedList<Node>();
14         queue.add(new Node(root, 0));
15         while(!queue.isEmpty()){
16             Node n = queue.poll();
17             if(n.node == null) continue;
18             if(dep < n.level){
19                 List<Integer> tmp = new ArrayList<Integer>();
20                 tmp.add(n.node.val);
21                 ret.add(tmp);
22                 dep++;
23             }else{
24                 ret.get(dep).add(n.node.val);
25             }
26             if(n.node.left != null) queue.add(new Node(n.node.left, n.level + 1));
27             if(n.node.right != null) queue.add(new Node(n.node.right, n.level + 1));
28         }
29         return ret;
30     }
31 }