P1827 美国血统 American Heritage题解复盘

USACO 3.4 家谱树已知中序前序求后序题解复盘基本信息项目内容题目编号、来源USACO Section 3.4 / 洛谷 P1030训练层级A 二叉树遍历知识版块二叉树、递归、字符串处理解题前・关键信号识别维度分析目标、约束、底层结构目标给定二叉树的中序遍历和前序遍历求出后序遍历约束节点数 ≤ 26字母表示底层结构前序第一个字符是根中序中根的位置将左右子树分开递归处理。数据规模节点数 ≤ 26O(n²) 完全可行。候选算法和依据递归 字符串切割依据前序遍历第一个字符 根节点在中序遍历中找到根的位置左边是左子树右边是右子树递归处理左右子树最后输出根后序左→右→根。复杂度预判时间复杂度 O(n²)每次 find 扫描 substr 复制n ≤ 26 完全足够空间复杂度 O(n²)每次递归创建新字符串。解题后・外化复盘维度内容实现结构 / 核心思路第一步读入中序 inor 和前序 pre第二步定义递归函数 work(pre, inor)若 pre 为空则返回第三步取 pre[0] 为根在 inor 中找到根的位置 k第四步删除 pre 的第一个字符第五步切割leftpre pre[0…k-1]rightpre pre[k…end]leftinor inor[0…k-1]rightinor inor[k1…end]第六步递归 work(leftpre, leftinor) 和 work(rightpre, rightinor)第七步输出根后序左→右→根。错因回溯1. 忘记处理空字符串的递归出口导致无限递归或越界2. 切割时左右子树的边界搞混特别是右子树的起点是 k 还是 k13. 前序删除根后左右子树的分配依据是中序中左子树的大小 k4. 输入顺序是先中序再前序容易读反。边界和易错点1. 递归出口if (pre.empty()) return;2. 中序中根的位置 k 同时是左子树的大小3. 前序删除根后左子树取前 k 个右子树取剩下的4. 中序左子树取前 k 个右子树从 k1 开始5. 字符串长度 ≤ 26用substr没问题6. 用string::find()查找字符位置。下次看到什么信号我应该想到这个方法看到「已知两种遍历求第三种遍历」用递归 字符串切割看到「前序中序→后序」前序第一个是根中序切分左右。AC 完整代码#includeiostream#includestringusingnamespacestd;string pre,inor;voidwork(string pre,string inor){if(pre.empty())return;charrootpre[0];intkinor.find(root);pre.erase(pre.begin());string leftprepre.substr(0,k);string leftinorinor.substr(0,k);string rightprepre.substr(k);string rightinorinor.substr(k1);work(leftpre,leftinor);work(rightpre,rightinor);coutroot;}intmain(){cininorpre;work(pre,inor);coutendl;return0;}