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

• step 1：首先判断二叉树是否为空，空树没有遍历结果。
• step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
• step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
• step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
• step 5：访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。

/**
 * 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
        vector<vector<int>> res;
        if(!root)
            return res;//如果是空，则直接返回空vector
        TreeNode *p;
        //队列存储，进行层次遍历
        queue<TreeNode*> q;
        q.push(root);
        TreeNode *cur;
        while(!q.empty())
        {
            //记录二叉树的某一行
            vector<int> row;
            int n = q.size();
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0;i<n;i++)
            {
                cur = q.front();
                q.pop();
                row.push_back(cur->val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(cur->left != nullptr)
                    q.push(cur->left);
                if(cur->right != nullptr)
                    q.push(cur->right);
            }
            //每一层加入输出
            res.push_back(row);
        }
        return res;

    }
};