徐州开发区中学网站,保定比较好的网站建设公司,百度添加网站,福州市城乡建设网站张麒蛰codevs 1029 遍历问题 时间限制: 1 s空间限制: 128000 KB题目等级 : 钻石 Diamond题目描述 Description我们都很熟悉二叉树的前序、中序、后序遍历#xff0c;在数据结构中常提出这样的问题#xff1a;已知一棵二叉树的前序和中序遍历#xff0c;求它的后序遍历#xff0c;… codevs 1029 遍历问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 我们都很熟悉二叉树的前序、中序、后序遍历在数据结构中常提出这样的问题已知一棵二叉树的前序和中序遍历求它的后序遍历相应的已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序你却不能确定其中序遍历序列考虑如下图中的几棵二叉树 所有这些二叉树都有着相同的前序遍历和后序遍历但中序遍历却不相同。 输入描述 Input Description 输入文件共2行第一行表示该树的前序遍历结果第二行表示该树的后序遍历结果。输入的字符集合为{a-z}长度不超过26。 输出描述 Output Description 输出文件只包含一个不超过长整型的整数表示可能的中序遍历序列的总数。 样例输入 Sample Input abc cba 样例输出 Sample Output 4 1 /*虽然题目说要用树形DP或者搜索但是如果对树的结构了解够深的话也可以直接做。2 很明显已知一棵二叉树的前序遍历和后序遍历判断中序遍历时其可能性只与没有兄弟节点的叶节点的位置有关。3 假设没有兄弟节点的叶节点共有n个则可能性边有2^n个。就不证明了4 那么如何计算n的值呢5 下面有一个性质6 一棵二叉树的前序遍历a1a2a3...ai和后序遍历b1b2b3...bi有一种关系7 没有兄弟节点的叶节点的根 在a序列下标为i 在b序列下标为j8 则有 a[i-1] b[j1]9 这是因为当根只有一棵子树时前序和后序遍历都是先遍历它的孩子而且是唯一的一个孩子所以相对位置是一样的。
10 */
11 #includeiostream
12 using namespace std;
13 string pre,hou;
14 int lenpre,lenhou;
15 int ans0;
16 int main()
17 {
18 cinprehou;
19 lenprepre.length()-1;
20 lenhouhou.length()-1;
21 for(int i1;ilenpre;i)
22 for(int j0;jlenhou-1;j)
23 if(pre[i]hou[j]pre[i-1]hou[j1])
24 ans;
25 cout(long long)(1ans)endl;
26 return 0;
27 } 转载于:https://www.cnblogs.com/c1299401227/p/5573830.html
