题解 | #求二叉树的层序遍历#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        //如果是空树直接返回
        if(root==nullptr)
            return vector<vector<int> >();

        //使用两个队列，分别储存当前层，和下一层
        queue<TreeNode*> q1;//queue容器一般使用pop(),push(),front()四个函数
        q1.push(root);
        queue<TreeNode*> q2;
        TreeNode* bt;
        

        //储存结果
        vector<int> temp;
        vector<vector<int> > res;



        while(q1.empty()!=1||q2.empty()!=1)
        {
           
           //处理当前层的元素，包括遍历和放入下一层
            while(q1.empty()!=1)
            { 
                bt=q1.front();
                q1.pop();
                temp.push_back(bt->val);
                if(bt->left!=nullptr)
                {
                    q2.push(bt->left);
                }
                if(bt->right!=nullptr)
                {
                    q2.push(bt->right);
                }
            }


            //保存当前层结果
            if(temp.empty()!=1)
            {
                res.push_back(temp);
                temp.clear();
            }


            //处理下一层
            while(q2.empty()!=1)
            { 
                bt=q2.front();
                q2.pop();
                temp.push_back(bt->val);
                if(bt->left!=nullptr)
                {
                    q1.push(bt->left);
                }
                if(bt->right!=nullptr)
                {
                    q1.push(bt->right);
                }
            }


            //保存下一层层结果
            if(temp.empty()!=1)
            {
                res.push_back(temp);
                temp.clear();
            }

        
        }

        return res;
    }
};

使用两个队列循环保存当前层和下一层，并且遍历