12.12 - 二叉树的层序遍历 C语言函数指针和指针函数的区别-编程实验室

1.二叉树的层序遍历

a.核心思想

b.思路

c.步骤

2.C语言函数指针和指针函数的区别

a.函数指针

b.指针函数

c.核心区别

1.二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-level-order-traversal/

/** * 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>> retvv; // 1. 处理特殊情况 if(root == nullptr) return retvv; // 2. 创建队列用于BFS，初始加入根节点 queue<TreeNode*> q; q.push(root); // 3. BFS主循环：队列非空时持续遍历 while(!q.empty()) { // 记录当前层节点数（关键：队列此时的大小就是当前层的节点总数） int levelsize = q.size(); vector<int> curv; for(int i = 0; i < levelsize; i++) { // 取出队首节点并移除 TreeNode* node = q.front(); q.pop(); // 保存该层的节点 curv.push_back(node->val); // 非空节点入队 if(node->left) q.push(node->left); if(node->right) q.push(node->right); } retvv.push_back(curv); } return retvv; } };

a.核心思想

利用广度优先搜索（BFS）的策略，按层次依次访问二叉树的节点，将每一层的节点值收集起来，形成层序遍历的结果。

b.思路

通过队列来辅助实现广度优先搜索。首先将根节点入队，然后在队列不为空的情况下，循环取出队列中的节点，将其值加入当前层的结果列表，并将其存在的左右子节点依次入队，当处理完当前层的所有节点后，将当前层的结果列表加入最终结果中。

c.步骤

① 初始化一个队列，将二叉树的根节点入队。
② 初始化一个结果列表用于存储层序遍历的结果。
③ 当队列不为空时，重复以下步骤：
获取当前队列的大小，即当前层的节点数。
初始化一个临时列表用于存储当前层的节点值。
循环当前层的节点数次，每次从队列中取出一个节点，将其值加入临时列表，并将其左右子节点（如果存在）入队。
将临时列表加入结果列表。
④ 返回结果列表。