本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P1229 遍历问题 - 洛谷
【题目描述】
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
【输入】
共两行，第一行表示该二叉树的前序遍历结果s 1 s_1s1，第二行表示该二叉树的后序遍历结果s 2 s_2s2。
保证至少存在一棵二叉树满足给出的信息，s 1 , s 2 s _ 1, s _ 2s1,s2中只含小写字母，且在某个字符串中不存在相同的字母。
【输出】
输出可能的中序遍历序列的总数，结果不超过2 63 − 1 2^{63}-1263−1。
【输入样例】
abc cba【输出样例】
4【算法标签】
《洛谷 P1229 遍历问题》 #树形数据结构#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int重新定义为long long类型，防止溢出string a,b;// 定义两个字符串a和bintcnt,ans=1;// cnt: 计数器，记录符合条件的相邻字符对数量；ans: 最终结果，初始为1signedmain()// 因为使用了#define int long long，所以用signed main{cin>>a>>b;// 输入两个字符串a和b// 双重循环遍历两个字符串中的所有相邻字符对for(inti=0;i<=a.size()-2;i++)// 遍历字符串a，从第0个字符到倒数第2个字符for(intj=0;j<=b.size()-2;j++)// 遍历字符串b，从第0个字符到倒数第2个字符{// 检查条件：a中相邻的两个字符是否等于b中相邻两个字符的逆序if(a[i]==b[j+1]&&a[i+1]==b[j])// 如果a[i]==b[j+1]且a[i+1]==b[j]cnt++;// 计数器加1}// 计算2的cnt次方for(inti=1;i<=cnt;i++)// 循环cnt次ans*=2;// ans乘以2，即计算2^cntcout<<ans<<endl;// 输出结果return0;// 程序正常结束}【运行结果】
abc cba 4
