博客

我们知道二叉树的层次遍历即为按照每一层从左到右的顺序遍历二叉树，先从最简单的层次遍历输出二叉树每个节点的值来说，需要用到queue队列的先进先出的原则来输出

void cinout(TreeNode* root) {   
       if(root==NULL)return ;  若根节点为空则返回
       queue<TreeNode*>dui;    创建一TreeNode*类型的队列
       dui.push(root);         若根节点不为空则无条件的将其加入队列
       while(!dui.empty()){    终止条件为队列为空
               TreeNode*first=dui.front();
               dui.pop();
               cout<<first->val<<" ";  将其值输出
               if(first->left)dui.push(first->left); 
               if(first->right)dui.push(first->right);
       }
    }

若是将二叉树的每一层输出而并非一个一个的输出，代码模板如下

vector<vector<int>> levelcinout(TreeNode* root) {
       vector<vector<int>>vv; 
       if(root==NULL)return vv;
       queue<TreeNode*>dui;
       dui.push(root);
       while(!dui.empty()){
           int size=dui.size();
           vector<int>v;
           for(int i=0;i<size;i++){
               TreeNode*first=dui.front();
               dui.pop();
               v.push_back(first->val);
               if(first->left)dui.push(first->left);
               if(first->right)dui.push(first->right);
       }
       vv.push_back(v);
    }