LeetCode 102. Binary Tree Level Order Traversal 二叉树的层次遍历 C++

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,null,null,15,7]

return its level order traversal as:

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

二叉树的层次遍历使用队列来实现，很大程度上类似于求树的最大深度。

第一种解法：开始时当前结点数curLevelCount=1,nextLevelCount=0,根据curLevelCount来输入每一层的结点值，当其左右子树存在时，将左右子树存入队列，并nextLevelCount++，每弹出一个当前层的结点时，curLevelCount--，当其为0时，再创建一个新的vector。

C++：

 1 vector<vector<int>> levelOrder(TreeNode* root) {
 2         vector<vector<int>> res={};
 3         queue<TreeNode*> q;
 4         if(!root)
 5             return res;
 6         q.push(root);
 7         int curLevelCount=1,nextLevelCount=0;
 8         vector<int> temp={};
 9         while(!q.empty()){
10             TreeNode* cur=q.front();
11             temp.push_back(cur->val);
12             q.pop();
13             curLevelCount--;            
14             if(cur->left){
15                 q.push(cur->left);
16                 nextLevelCount++;
17             }
18             if(cur->right){
19                 q.push(cur->right);
20                 nextLevelCount++;
21             }
22             if(curLevelCount==0){
23                 res.push_back(temp);
24                 temp={};
25                 curLevelCount=nextLevelCount;
26                 nextLevelCount=0;
27             }
28         }
29         return res;
30     }

第二种方法不用参数计算每一层结点个数，利用for循环，每一层时利用队列的大小来计算每一层的结点数。两层循环嵌套，效率比较低。

 1 vector<vector<int>> levelOrder(TreeNode* root) {
 2         vector<vector<int>> res={};
 3         queue<TreeNode*> q;
 4         if(!root)
 5             return res;
 6         q.push(root);
 7         while(!q.empty()){
 8             vector<int> temp={};
 9             for(int i=q.size();i>0;i--){
10                 TreeNode* cur=q.front();
11                 temp.push_back(cur->val);
12                 q.pop();       
13                 if(cur->left)
14                     q.push(cur->left);
15                 if(cur->right)
16                     q.push(cur->right);
17             }
18             res.push_back(temp);
19         }
20         return res;
21     }