lintcode-dfs实现二叉树的层序遍历

 1 class Solution {
 2     /**
 3      * @param root: The root of binary tree.
 4      * @return: Level order a list of lists of integer
 5      */
 6     struct node{
 7         TreeNode* tn;
 8         int cnt;
 9         node(TreeNode* tn, int cnt){
10                 this->tn = tn;
11                 this->cnt = cnt;
12         }
13     };
14 
15 public:
16     void dfs(vector<vector<int>> &ans, queue<node*> &que){
17             if(que.empty()) return ;
18             node* now = que.front();
19             que.pop();
20 
21             if(now->tn->left) que.push(new node(now->tn->left, now->cnt + 1));
22             if(now->tn->right) que.push(new node(now->tn->right, now->cnt + 1));
23             
24             if((int)ans.size() - 1 < now->cnt){
25                 vector<int> v(1,now->tn->val);
26                 ans.push_back(v);
27 
28             } else {
29                 ans[now->cnt].push_back(now->tn->val);
30             }
31 
32             dfs(ans, que);
33 
34     }
35     vector<vector<int>> levelOrder(TreeNode *root) {
36         // write your code here
37         vector<vector<int>> ans;
38         if(root == NULL) return ans;
39         queue<node*> que;
40         que.push(new node(root,0));
41         dfs(ans, que);
42         return ans;
43     }
44 };