P1030 [NOIP 2001 普及组] 求先序排列

记录144#includebits/stdc.h using namespace std; // 使用标准命名空间std string in_str,post_str; // 全局变量存储中序和后序遍历字符串 // 递归函数根据中序和后序的区间输出前序遍历 // l1,r1: 中序遍历字符串的左右边界 [l1,r1] // l2,r2: 后序遍历字符串的左右边界 [l2,r2] void dfs(int l1,int r1,int l2,int r2) { // 递归终止条件如果区间无效左边界大于右边界说明子树为空直接返回 if(l1r1) return; // 1. 找根节点后序遍历的最后一个字符就是根 char rootpost_str[r2]; // 2. 在中序遍历中找到根节点的位置 p int pl1; while(in_str[p]!root) { p; } // 计算左子树的节点个数 int left_sizep-l1; // 3. 输出根节点前序遍历根左右根放在最前面输出 coutroot; // 4. 递归处理左子树 // 中序左子树范围[l1,p-1] // 后序左子树范围[l2,l2left_size-1] dfs(l1,p-1,l2,l2left_size-1); // 5. 递归处理右子树 // 中序右子树范围[p1,r1] // 后序右子树范围[l2left_size,r2-1] (注意r2是根要减1) dfs(p1,r1,l2left_size,r2-1); } int main() { // 主函数入口 ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); // 读入中序遍历和后序遍历 cinin_strpost_str; // 启动递归初始区间都是整个字符串的长度 dfs(0,in_str.size()-1,0,post_str.size()-1); cout\n; // 输出换行 return 0; }题目传送门https://www.luogu.com.cn/problem/P1030前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的二叉树遍历与递归重建问题其核心原理与“中序前序求后序”类似但细节上存在关键差异。核心原理在二叉树的三种遍历方式中后序遍历左-右-根的最后一个元素永远是当前子树的根节点而中序遍历左-根-右中根节点会将序列完美地分割为左子树和右子树两部分。利用这两个特性我们可以通过递归的方式不断地从字符串中“切”出左子树和右子树从而在逻辑上重建这棵二叉树。算法设计分治递归题目要求输出先序遍历根-左-右。我们不需要真正地在内存中构建出树的结构只需要在递归的过程中按照“先输出根节点 - 再递归处理左子树 - 最后递归处理右子树”的顺序进行操作即可直接得到先序遍历的结果。代码分块详细解释1. 头文件与全局变量定义#includebits/stdc.h using namespace std; // 使用标准命名空间std string in_str, post_str; // 全局变量存储中序和后序遍历字符串详细分析由于树的节点用唯一的大写字母表示且节点个数不超过 8 个使用string类型来存储遍历序列非常方便。将这两个字符串定义为全局变量可以避免在递归函数中反复传递庞大的字符串副本提高程序运行效率。2. 核心逻辑分治递归函数dfs// 递归函数根据中序和后序的区间输出前序遍历 // l1,r1: 中序遍历字符串的左右边界 [l1,r1] // l2,r2: 后序遍历字符串的左右边界 [l2,r2] void dfs(int l1, int r1, int l2, int r2) { // 递归终止条件如果区间无效左边界大于右边界说明子树为空直接返回 if(l1 r1) return; // 1. 找根节点后序遍历的最后一个字符就是根 char root post_str[r2]; // 2. 在中序遍历中找到根节点的位置 p int p l1; while(in_str[p] ! root) { p; } // 计算左子树的节点个数 int left_size p - l1; // 3. 输出根节点前序遍历根左右根放在最前面输出 cout root; // 4. 递归处理左子树 // 中序左子树范围[l1, p-1] // 后序左子树范围[l2, l2left_size-1] dfs(l1, p-1, l2, l2left_size-1); // 5. 递归处理右子树 // 中序右子树范围[p1, r1] // 后序右子树范围[l2left_size, r2-1] (注意r2是根要减1) dfs(p1, r1, l2left_size, r2-1); }详细分析这是本题的灵魂所在完美体现了“分治”思想。确定根节点与“前序找根”不同后序遍历的特点是“根节点在最后面”所以当前后序区间的最后一个字符post_str[r2]必定是当前子树的根。划分左右子树在中序遍历区间[l1, r1]中找到这个根节点的位置p。根据中序遍历“左-根-右”的规则[l1, p-1]这一段全是左子树的节点[p1, r1]这一段全是右子树的节点。计算子树大小左子树的节点个数left_size p - l1。这个数值至关重要因为它帮助我们在后序遍历中准确切分出左右子树的区间。后序遍历中左子树节点在前右子树节点在后最后是根。所以左子树在后序中的区间是[l2, l2left_size-1]右子树是[l2left_size, r2-1]注意右边界r2是根节点必须减 1。先序输出函数先cout root输出根节点然后递归处理左子树最后递归处理右子树。这种“根左右”的输出顺序恰好就是先序遍历的定义。3. 主函数输入处理与启动递归int main() { ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); // 读入中序遍历和后序遍历 cin in_str post_str; // 启动递归初始区间都是整个字符串的长度 dfs(0, in_str.size()-1, 0, post_str.size()-1); cout \n; // 输出换行 return 0; }详细分析主函数非常简洁主要负责读取输入并启动递归。dfs(0, in_str.size()-1, 0, post_str.size()-1)表示最初我们要处理的是完整的中序和后序字符串左右边界分别是0和字符串长度-1。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点根节点定位char root post_str[r2]利用后序遍历特性提取当前子树的根确立了递归分治的基准点是划分左右子树的前提区间划分while(in_str[p]!root)在中序遍历中定位根节点的位置 p利用中序遍历特性将序列完美切割为左子树和右子树子树大小计算int left_size p - l1计算左子树包含的节点数量桥接中序与后序帮助在后序字符串中准确切分出左右子树的区间根节点输出cout root在递归左右子树之前输出根遵循先序遍历“最先根”的规则直接拼接出最终答案递归左子树dfs(l1, p-1, l2, ...)递归处理左半部分区间深入树的左侧分支遵循先序遍历“后左”的规则递归右子树dfs(p1, r1, ...left_size, r2-1)