leetcode 链接：二叉树的层序遍历

题目

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解答 & 代码

注意：层序遍历一定要先判定一下特殊情况，即 **root** 是否为 **nullptr**

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(!root)                    // 特殊情况：二叉树为空，返回空数组
            return result;

        queue<TreeNode*> nodeQ;        // 队列，用于层序遍历存储结点指针
        nodeQ.push(root);            // 将根节点压入队列
        while(!nodeQ.empty())
        {
            int nodeNum = nodeQ.size();        // 当前层节点数
            vector<int> levelList;            // 存储这一层的节点值
            for(int i = 0; i < nodeNum; ++i)
            {
                // 每次从链表头部弹出一个节点
                TreeNode* node = nodeQ.front();
                nodeQ.pop();
                levelList.push_back(node->val);

                if(node->left)                // 左孩子不为空才压入队列
                    nodeQ.push(node->left);
                if(node->right)                // 右孩子不为空才压入队列
                    nodeQ.push(node->right);
            }
            result.push_back(levelList);
        }
        return result;
    }
};

复杂度分析：设二叉树共 N 个节点

• 时间复杂度 O(N)：遍历每个节点一次
• 空间复杂度 O(N)：队列 nodeQ 中存储的节点个数不会超过 N

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：12.3 MB, 在所有 C++ 提交中击败了 42.80% 的用户