102. 二叉树的层序遍历

【题目】：102. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) {
            return {};
        }
        queue<TreeNode*> q;
        vector<vector<int>> res;
        q.push(root);
        while(!q.empty()) {
            vector<int> tempVec; // 存储一整行的数据
            int n = q.size();
            for(int i = 0; i < n; ++i) { // 遍历q队列（此时q队列中存储一层的数据 -> 全部出队）
                TreeNode* node = q.front();
                q.pop();
                // 入队
                if(node->left != nullptr) {
                    q.push(node->left);
                }
                if(node->right != nullptr) {
                    q.push(node->right);
                }

                tempVec.push_back(node->val); 
            }
            res.push_back(tempVec);
        }
        return res;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

这题的难点在于，题目要求是要返回一个二维数组，那怎么去记录每一层的节点呢？在每一次循环的时候，当前队列中的节点就是这一层的节点，因此可以用一个tempVec来存储当前队列中的数据，在每一轮的循环结束时，把tempVec插入结果数组中。