【练习】【二叉树】力扣热题100 102. 二叉树的层序遍历

题目

102. 二叉树的层序遍历

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

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

来源：力扣热题100 102. 二叉树的层序遍历

思路（注意事项）

• 队列定义为指针类型

核心

• 定义队列
• 根节点入队
• 队列非空时循环
• • 遍历队列中的所有元素并加入临时结果集
• • 将临时结果集加入最终结果集

纯代码

class Solution {
private:
    vector<vector<int>> ans;  
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty())
        {
            int n = q.size();
            vector<int> path;
            while (n --)
            {
                auto tmp = q.front();
                q.pop();
                path.push_back(tmp -> val);

                if (tmp -> left) q.push(tmp -> left);
                if (tmp -> right) q.push(tmp -> right);
            }
            ans.push_back(path);
        }
        return ans;
    }
};

题解（加注释）

class Solution {
private:
    vector<vector<int>> ans; // 用于存储层序遍历的结果

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 如果根节点为空，直接返回空结果
        if (!root) return {};

        // 使用队列辅助层序遍历
        queue<TreeNode*> q;
        q.push(root); // 将根节点入队

        // 开始层序遍历
        while (!q.empty()) {
            int n = q.size(); // 当前层的节点数
            vector<int> path; // 用于存储当前层的节点值

            // 遍历当前层的所有节点
            while (n--) {
                TreeNode* tmp = q.front(); // 取出队头节点
                q.pop(); // 将队头节点出队

                path.push_back(tmp->val); // 将当前节点的值加入当前层的路径

                // 如果当前节点有左子节点，将左子节点入队
                if (tmp->left) q.push(tmp->left);
                // 如果当前节点有右子节点，将右子节点入队
                if (tmp->right) q.push(tmp->right);
            }

            // 将当前层的路径加入结果集
            ans.push_back(path);
        }

        // 返回层序遍历的结果
        return ans;
    }
};