企业官网建设流程全解析

csp信奥赛C++高频考点专项训练之字符串 --【字符串综合】：遍历问题

题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

BB%EF%BC%89%5CP1229%E5%9B%BE%E4%BE%8B.png&pos_id=img-kXoQ0BhS-1778906348869)

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

共两行，第一行表示该二叉树的前序遍历结果s 1 s_1s1​，第二行表示该二叉树的后序遍历结果s 2 s_2s2​。

保证至少存在一棵二叉树满足给出的信息，s 1 , s 2 s _ 1, s _ 2s1​,s2​中只含小写字母，且在某个字符串中不存在相同的字母。

输出格式

输出可能的中序遍历序列的总数，结果不超过2 63 − 1 2^{63}-1263−1。

输入输出样例 1

输入 1

abc cba

输出 1

4

思路分析

给定二叉树的前序和后序遍历序列，中序遍历不唯一的原因是某些结点只有一个子结点时，无法确定该子结点是左孩子还是右孩子。
对于每个只有一个子结点的结点，中序遍历有两种可能，且不同结点的选择相互独立，因此可能的中序遍历总数为2 单子结点个数 2^{\text{单子结点个数}}2单子结点个数。

如何统计单子结点个数？

• 前序遍历中，若结点root只有一个子结点，则该子结点必为root的下一个结点child = pre[i+1]。
• 后序遍历中，root的前一个结点必为child（因为子树的后序序列以child结尾，接着是root）。
• 因此，只需检查post[pos(root)-1] == child是否成立，其中pos(root)是root在后序中的位置。
• 遍历前序序列（除最后一个结点），统计满足上述条件的次数cnt，答案即为1 << cnt。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){string a,b;// a前序遍历，b后序遍历cin>>a>>b;intn=a.size();// 结点个数intidx[256]={0};// 记录每个字符在后序中的下标for(inti=0;i<n;i++)idx[b[i]]=i;// 建立映射longlongans=1;// 结果初始为1for(inti=0;i<n-1;i++){// 遍历前序，最后一个结点无子结点，无需处理charroot=a[i];// 当前结点charchild=a[i+1];// 前序中紧跟着的结点（可能是左子或唯一子）// 若child在后序中恰好在root前一位，则root只有一个子结点，答案乘2if(idx[child]==idx[root]-1)ans<<=1;}cout<<ans<<endl;return0;}

功能分析

• 输入处理：读入两行字符串，分别代表前序和后序遍历序列（无重复字符）。
• 映射建立：用数组idx记录每个字符在后序序列中的位置，以便 O(1) 查询。
• 单子结点统计：遍历前序序列的每个非尾结点，检查其下一个结点是否在后序中位于该结点之前一位。若是，则计数一次（等价于ans左移一位乘 2）。
• 输出结果：最终ans即为可能的中序遍历总数，保证在long long范围内（题目保证结果不超过2 63 − 1 2^{63}-1263−1。
• 时间复杂度：O(n)，其中 n 为字符串长度。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}