*

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

     public:

     vector<vector<int> > levelOrder(TreeNode *root) {

         vector<vector<int>> result;

         traverse(root,,result);

        std::reverse(result.begin(),result.end());//比层序遍历1多此一行

         return result;

     }

     void traverse(TreeNode *root,size_t level,vector<vector<int>> &result)

     {

         if(root==nullptr) return;

         if(level>result.size()) result.push_back(vector<int>());

         result[level-].push_back(root->val);

         traverse(root->left,level+,result);

         traverse(root->right,level+,result);

     }

 };

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

  /*常规层序遍历思想，每层入队结束压入一个空节点，作为标志*/

 class Solution {

 public:

     vector<vector<int> > levelOrder(TreeNode *root) {

         vector<vector<int>> vec_vec_tree;//创建空vector,存放最后返回的遍历二叉树的值

         vector<int> level;//创建空的vector，存放每一层的遍历二叉树的值

         TreeNode *p=root;

         if(p==nullptr) return vec_vec_tree;//如果二叉树空，返回空vector<vector<int>>

         queue<TreeNode *> queue_tree;//创建一个空队列

         queue_tree.push(p);//root节点入队列

         queue_tree.push(nullptr);//空节点入队列

         while(!queue_tree.empty())//直到队列为空

         {

             p=queue_tree.front();    //头结点取值，并出队列

             queue_tree.pop();

             if(p==nullptr&&!level.empty())//节点为空并且队列不为空

             {

                 queue_tree.push(nullptr);//入队空节点，与下一层隔开

                 vec_vec_tree.push_back(level);//已遍历的层入队

                 level.clear();//清空vecor level

             }

             else if(p!=nullptr)//如果节点不空

             {

             level.push_back(p->val);//遍历

             if(p->left) queue_tree.push(p->left);//若有左右孩子，则入队列

             if(p->right) queue_tree.push(p->right);//注意入队顺序：先左后右

             }

         }

         std::reverse(vec_vec_tree.begin(),vec_vec_tree.end());//比层序遍历1多此一行

         return vec_vec_tree;

     }

 };

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

  /*两个队列实现*/

 class Solution {

 public:

     vector<vector<int> > levelOrder(TreeNode *root) {

         vector<vector<int> > result;

         if(root == nullptr) return result;

          queue<TreeNode*> current, next;//两个队列，保存当层（current）和下层（next）节点

         vector<int> level; // 存放每层的节点值

         current.push(root);

         while (!current.empty())//直到二叉树遍历完成

         {

             while (!current.empty())//直到本层二叉树遍历完成

             {

                 TreeNode* node = current.front();//取队首节点，出队列

                 current.pop();

                 level.push_back(node->val);//访问节点值

                 if (node->left != nullptr) next.push(node->left);//若存在左右节点，则压入next队列中

                 if (node->right != nullptr) next.push(node->right);//注意入队顺序为先left后right

             }

             result.push_back(level);//压入总vector

             level.clear();//清vector

             swap(next, current);//next队列和current队列交换

         }

         std::reverse(result.begin(),result.end());//比层序遍历1多此一行

         return result;

         }

     };