C++中容器queue的使用

• front(),back()访问队首队尾元素；pop(),push()出队和入队

题目：

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
    / \
  15 7
返回其层次遍历结果：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

用队列实现二叉树的层次遍历

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrder(TreeNode* root) {
13         vector<vector<int>> res;
14         if(!root) return res;
15         queue<TreeNode*> qu;
16         qu.push(root);
17         while(!qu.empty()){
18             vector<int> tmp;
19             int len=qu.size();
20             for(int i=0;i<len;++i){   
21                TreeNode *node=qu.front();
22                qu.pop();
23                tmp.push_back(node->val);
24                if(node->left) qu.push(node->left);
25                if(node->right) qu.push(node->right);
26             }
27             res.push_back(tmp);
28         }
29         return res;
30     }
31 };

注意 

使用队列层次遍历二叉树，先把结点入队，如果队列不为空，输出队头元素。如果输出元素左右孩子不为空，依次把左右孩子入队。