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

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

#include <queue>
#include <vector>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int> > it;
        if(root==nullptr)
        {
            return it;
        }
        // 广度优先搜索用队列存储中间对象，这里存储的是每一层的结点。使用队列是因为它先进先出的特性，每一次循环要把之前的结点删除掉，将下一层结点添加进去
        queue<TreeNode*> qu;
        TreeNode *node=root;
        qu.push(root);
        while (qu.empty()==false) {
            vector<int> temp;
            int _size = qu.size();
            // 这里选择qu.size层循环的原因是，每一次更新下一层的结点到列表中时，都需要删除原来列表中的元素，原来上一次的列表元素数量就是qu.size
            // 并且这个qu.size循环必须用一个整数在for循环外部定义。如果直接用qu.size的话，因为for循环内部有对queue的操作，所以for循环次数是不断地在动态变化的
            for (int i=0; i<_size; i++) {
                // 第一层循环里只有root一个结点，要是删除了下面就无法执行，所以必须有一个临时结点来保存每一层的第一个结点
                node=qu.front();
                // 先要把原来的结点删除，才能向vector里push
                qu.pop();
                temp.push_back(node->val);
                // 判空执行，养成好习惯！
                if(node->left!=nullptr)qu.push(node->left);
                if(node->right!=nullptr)qu.push(node->right);
            }
            it.push_back(temp);
            temp.clear();
        }
        return it;
    }
};