NC15 求二叉树的层序遍历

 1 /**
 2  * struct TreeNode {
 3  *    int val;
 4  *    struct TreeNode *left;
 5  *    struct TreeNode *right;
 6  * };
 7  */
 8 
 9 class Solution {
10 public:
11     /**
12      * 
13      * @param root TreeNode类 
14      * @return int整型vector<vector<>>
15      */
16     vector<vector<int> > levelOrder(TreeNode* root) {
17         // write code here
18         if(root==nullptr) return vector<vector<int>>{};
19         // 层次遍历用队列而不用vector是由于queue比较少占用内存
20         queue<TreeNode*> tq;tq.push(root);
21         vector<int> lc={1};
22         //vector<vector<TreeNode*>> tres={vector<TreeNode*>{root}};
23         vector<vector<int>> res={vector<int>{root->val}};
24         while(!tq.empty()){    // ...
25             int prelev=lc.back();
26             vector<int> tmp; int nextlev=0;
27             for(int i=0;i<prelev;++i){
28                 // 父出队，子入队
29                 TreeNode* curN=tq.front();tq.pop();
30                 if(curN->left){
31                     tq.push(curN->left);
32                     nextlev++;
33                     tmp.push_back(curN->left->val);
34                 } 
35                 if(curN->right){
36                     tq.push(curN->right);
37                     nextlev++;
38                     tmp.push_back(curN->right->val);
39                 } 
40             }
41             if(!tmp.empty()){
42                 res.push_back(tmp);lc.push_back(nextlev);
43             }
44         }
45         return res;
46     }
47 };