记录144

#include<bits/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(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,l2+left_size-1] dfs(l1,p-1,l2,l2+left_size-1); // 5. 递归处理右子树 // 中序右子树范围：[p+1,r1] // 后序右子树范围：[l2+left_size,r2-1] (注意：r2是根，要减1) dfs(p+1,r1,l2+left_size,r2-1); } 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; }

题目传送门https://www.luogu.com.cn/problem/P1030

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道非常经典的二叉树遍历与递归重建问题，其核心原理与“中序+前序求后序”类似，但细节上存在关键差异。

1. 核心原理：
   在二叉树的三种遍历方式中，后序遍历（左-右-根）的最后一个元素永远是当前子树的根节点；而中序遍历（左-根-右）中，根节点会将序列完美地分割为左子树和右子树两部分。利用这两个特性，我们可以通过递归的方式，不断地从字符串中“切”出左子树和右子树，从而在逻辑上重建这棵二叉树。

2. 算法设计（分治递归）：
   题目要求输出先序遍历（根-左-右）。我们不需要真正地在内存中构建出树的结构，只需要在递归的过程中，按照“先输出根节点 -> 再递归处理左子树 -> 最后递归处理右子树”的顺序进行操作，即可直接得到先序遍历的结果。

代码分块详细解释

1. 头文件与全局变量定义

#include<bits/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, l2+left_size-1] dfs(l1, p-1, l2, l2+left_size-1); // 5. 递归处理右子树 // 中序右子树范围：[p+1, r1] // 后序右子树范围：[l2+left_size, r2-1] (注意：r2是根，要减1) dfs(p+1, r1, l2+left_size, r2-1); }

• 详细分析：这是本题的灵魂所在，完美体现了“分治”思想。
  • 确定根节点：与“前序找根”不同，后序遍历的特点是“根节点在最后面”，所以当前后序区间的最后一个字符post_str[r2]必定是当前子树的根。
  • 划分左右子树：在中序遍历区间[l1, r1]中找到这个根节点的位置p。根据中序遍历“左-根-右”的规则，[l1, p-1]这一段全是左子树的节点，[p+1, r1]这一段全是右子树的节点。
  • 计算子树大小：左子树的节点个数left_size = p - l1。这个数值至关重要，因为它帮助我们在后序遍历中准确切分出左右子树的区间。后序遍历中，左子树节点在前，右子树节点在后，最后是根。所以左子树在后序中的区间是[l2, l2+left_size-1]，右子树是[l2+left_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。

核心逻辑总结表