B3642 二叉树的遍历

记录161#includebits/stdc.h using namespace std; const int N1e65; int n; int l[N],r[N]; //静态数组存储二叉树 void preOrder(int u){ if(u0) return; coutu ; preOrder(l[u]); preOrder(r[u]); } void inOrder(int u){ if(u0) return; inOrder(l[u]); coutu ; inOrder(r[u]); } void postOrder(int u){ if(u0) return; postOrder(l[u]); postOrder(r[u]); coutu ; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1;in;i) cinl[i]r[i]; preOrder(1); cout\n; inOrder(1); cout\n; postOrder(1); return 0;//结束程序 }题目传送门https://www.luogu.com.cn/problem/B3642前言我是一名专注信奥赛GESP、CSP-J/S的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的二叉树遍历基础题重点考察对二叉树三种遍历方式前序、中序、后序的理解以及静态数组建图链式前向星思想的应用。问题转化静态数组建树题目给出了每个节点编号为 1∼n的左右子节点编号。由于节点编号是连续且已知的我们完全不需要使用指针或结构体来动态创建节点而是直接使用两个大小为 10651065 的整型数组l和r来存储。数组的下标代表当前节点的编号数组的值代表其左右子节点的编号。如果值为 0则表示该方向没有子节点。算法设计递归遍历二叉树的三种遍历方式本质上只是访问根节点的时机不同前序遍历先访问根节点再递归遍历左子树最后递归遍历右子树。中序遍历先递归遍历左子树再访问根节点最后递归遍历右子树。后序遍历先递归遍历左子树再递归遍历右子树最后访问根节点。在代码中我们只需将cout u ;这一行输出语句放在递归调用的不同位置即可实现三种遍历。代码分块详细解释1. 头文件、常量定义与全局数组#includebits/stdc.h using namespace std; const int N 1e6 5; int n; int l[N], r[N]; // 静态数组存储二叉树详细分析题目中节点数 nn 最大可达 106106 因此必须将数组开在全局区const int N 1e65防止在main函数内部定义导致栈内存溢出。l[N]和r[N]构成了这棵二叉树的“骨架”通过下标直接映射实现了 O(1)O(1) 的节点访问。2. 核心逻辑三种遍历的递归实现void preOrder(int u){ if(u 0) return; // 遇到空节点直接返回 cout u ; // 【根】先访问根节点 preOrder(l[u]); // 【左】递归遍历左子树 preOrder(r[u]); // 【右】递归遍历右子树 } void inOrder(int u){ if(u 0) return; inOrder(l[u]); // 【左】先递归遍历左子树 cout u ; // 【根】再访问根节点 inOrder(r[u]); // 【右】最后递归遍历右子树 } void postOrder(int u){ if(u 0) return; postOrder(l[u]); // 【左】先递归遍历左子树 postOrder(r[u]); // 【右】再递归遍历右子树 cout u ; // 【根】最后访问根节点 }详细分析这三个函数是代码的灵魂完美体现了递归的对称美。边界处理if(u 0) return;是递归的终止条件。因为题目规定 0 代表没有子节点所以当传入 0 时说明已经走到了叶子节点的外部必须立刻返回。输出时机正如思路中所述cout u ;的位置决定了遍历的类型。前序在递归前输出中序在两次递归之间输出后序在两次递归后输出。3. 主函数数据读入与遍历启动int main(){ ios::sync_with_stdio(false); // 关闭C与C标准流的同步 cin.tie(0); // 解除cin与cout的绑定 cin n; for(int i 1; i n; i) cin l[i] r[i]; // 读取每个节点的左右孩子 preOrder(1); // 题目明确根节点为1启动前序遍历 cout \n; inOrder(1); // 启动中序遍历 cout \n; postOrder(1); // 启动后序遍历 return 0; // 结束程序 }详细分析IO加速由于 nn 最大为 10^6 遍历过程中会产生大量的cout输出。如果不加ios::sync_with_stdio(false);和cin.tie(0);程序极大概率会因为 IO 瓶颈而超时TLE。建树过程for循环中由于输入的第 ii 行对应的就是编号为 ii 的节点我们直接将读入的左右孩子存入l[i]和r[i]即可无需任何复杂的指针操作。启动遍历题目保证根节点编号为 1因此直接以1为参数调用三个遍历函数并在每次遍历后输出换行符以满足格式要求。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点静态建树l[N],r[N]使用数组下标映射节点关系避免了动态分配内存指针的开销极大提高了建树和访问效率边界处理if(u 0) return;递归终止条件防止对空节点进行无效访问保证递归正确结束前序遍历cout在preOrder(l)之前按照“根 →→ 左 →→ 右”输出满足题目对第一行输出的要求中序遍历cout在两次递归之间按照“左 →→ 根 →→ 右”输出满足题目对第二行输出的要求后序遍历cout在postOrder(r)之后按照“左 →→ 右 →→ 根”输出满足题目对第三行输出的要求IO加速ios::sync_with_stdio(false)关闭流同步与绑定应对 106106 级别节点产生的大量输出防止程序超时