免费货源在线网站兖州网站建设推广

免费货源在线网站,兖州网站建设推广,郑州seo团队,新网站的宣传推广二叉树是数据结构中至关重要的非线性结构#xff0c;而层序遍历#xff08;Level Order Traversal#xff09;是二叉树遍历方式中极具代表性的一种 —— 它按照从上到下、从左到右的顺序逐层访问节点#xff0c;这种遍历方式也被称为 “广度优先遍历#xff08;BFS#x…二叉树是数据结构中至关重要的非线性结构而层序遍历Level Order Traversal是二叉树遍历方式中极具代表性的一种 —— 它按照从上到下、从左到右的顺序逐层访问节点这种遍历方式也被称为 “广度优先遍历BFS”。本文将从层序遍历的核心思想出发拆解具体实现逻辑并通过完整代码解析带你掌握二叉树层序遍历的实现方法。一、层序遍历的核心思想不同于前序、中序、后序遍历的 “深度优先” 思路沿着一条路径走到头再回溯层序遍历的核心是 “广度优先”先访问根节点所在的第一层再依次访问第二层的所有节点接着是第三层…… 直到遍历完所有层级。要实现这种 “逐层访问” 的逻辑关键在于借助队列Queue这一数据结构。队列的 “先进先出FIFO” 特性恰好能满足 “先访问的节点其左右子节点也先入队、先被访问” 的需求初始化队列将根节点入队循环处理队列中的节点每次取出当前队列中的所有节点即当前层的全部节点记录它们的值再将这些节点的左右子节点非空时依次入队重复上述过程直到队列为空此时所有层级已遍历完毕。二、完整代码实现与逐行解析以下是基于 C 实现的二叉树层序遍历代码我们将逐行拆解核心逻辑cpp运行/** * 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: vectorvectorint levelOrder(TreeNode* root) { // 存储最终结果每一个子数组对应一层的节点值 vectorvectorint result; // 空树直接返回空结果避免后续无效操作 if (root nullptr) return result; // 队列存储待遍历的节点核心数据结构 queueTreeNode* q; // 根节点入队作为遍历的起点 q.push(root); // 队列非空时说明还有未遍历的节点 while (!q.empty()) { // 关键记录当前层的节点数量队列此时的大小即为当前层节点数 int levelSize q.size(); // 存储当前层的所有节点值 vectorint currentLevel; // 遍历当前层的所有节点 for (int i 0; i levelSize; i) { // 取出队列头部节点当前层的下一个节点 TreeNode* node q.front(); q.pop(); // 记录当前节点值到当前层的结果中 currentLevel.push_back(node-val); // 左子节点非空则入队为下一层遍历做准备 if (node-left ! nullptr) { q.push(node-left); } // 右子节点非空则入队保持“左到右”的顺序 if (node-right ! nullptr) { q.push(node-right); } } // 将当前层的结果加入最终结果集 result.push_back(currentLevel); } return result; } };核心细节拆解空树判断代码开头先判断根节点是否为空若为空直接返回空的结果数组这是鲁棒性的体现避免后续对空指针的操作。队列的作用队列是层序遍历的核心它始终存储 “下一层待遍历的节点”。每次进入while循环时队列的大小恰好等于当前层的节点数量 —— 这是实现 “分层” 的关键。分层遍历的关键levelSize q.size()这一行是整个代码的精髓。因为进入while循环时队列中所有节点都属于同一层通过levelSize限定for循环的次数就能确保每次for循环只处理当前层的节点不会混入下一层的节点。子节点入队顺序先左子节点、后右子节点入队保证了遍历结果符合 “从左到右” 的层序要求。三、代码执行流程示例假设我们有一棵简单的二叉树plaintext3 / \ 9 20 / \ 15 7代码的执行流程如下初始化队列将根节点 3 入队队列[3]进入while循环levelSize1开启for循环i0取出节点 3记录值 3当前层数组[3]节点 3 的左子节点 9、右子节点 20 入队队列变为[9,20]for循环结束将 [3] 加入结果集结果[[3]]再次进入while循环队列非空levelSize2开启for循环i0取出节点 9记录值 9当前层数组[9]节点 9 无左右子节点队列变为[20]i1取出节点 20记录值 20当前层数组[9,20]节点 20 的左子节点 15、右子节点 7 入队队列变为[15,7]for循环结束将 [9,20] 加入结果集结果[[3],[9,20]]再次进入while循环队列非空levelSize2开启for循环i0取出节点 15记录值 15当前层数组[15]节点 15 无左右子节点队列变为[7]i1取出节点 7记录值 7当前层数组[15,7]节点 7 无左右子节点队列变为空for循环结束将 [15,7] 加入结果集结果[[3],[9,20],[15,7]]队列为空while循环结束返回最终结果。四、时间与空间复杂度分析时间复杂度O (n)。其中 n 是二叉树的节点总数。每个节点仅入队和出队一次遍历所有节点的时间复杂度为 O (n)其余操作如记录节点值均为常数级。空间复杂度O (n)。最坏情况下如满二叉树队列需要存储最后一层的所有节点最后一层的节点数最多为 n/2因此空间复杂度为 O (n)。五、总结二叉树的层序遍历是广度优先搜索BFS在树形结构中的典型应用其核心是借助队列的 “先进先出” 特性实现分层遍历。本文从核心思想出发拆解了完整的代码实现并通过示例分析了执行流程最后梳理了复杂度。掌握层序遍历不仅能解决二叉树的基础遍历问题还能延伸到诸多变种问题如 “按层打印二叉树并换行”“求二叉树的最大深度”“找二叉树某一层的最大值” 等。理解队列在其中的作用以及levelSize对分层的关键意义是攻克这类问题的核心。无论是面试中的算法题还是实际开发中的树形数据处理层序遍历都是必备的基础技能。希望本文能帮助你彻底理解并掌握这一经典算法。