1029 遍历问题

题目描述 Description

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

 

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

输入描述 Input Description

    输入文件共2行，第一行表示该树的前序遍历结果，第二行表示该树的后序遍历结果。输入的字符集合为{a-z}，长度不超过26。

输出描述 Output Description

    输出文件只包含一个不超过长整型的整数，表示可能的中序遍历序列的总数。

样例输入 Sample Input

abc

cba

样例输出 Sample Output

4

思路：

我们要知道如果一个节点既有左子树又有右子树，那么这个节点在前序遍历和后序遍历的结果中就确定了 也就是只有一种结构。 如果一个节点只有左子树或者只有右子树，那么这个节点和他唯一的儿子节点就有两种结构满足相同的前序遍历和后序遍历(如题干) 这个题目要我们求有多少种满足情况的二叉树，也就是让我们找有多少个节点只有一个子节点 那么我们怎么来处理？ 这里再次用到前序遍历和后续遍历的性质:一个节点和它唯一的子节点在前序遍历和后序遍历中出现的位置刚好相反

没有兄弟节点的叶节点的根 在pre序列下标为i， 在buf序列下标为j 则有  pre[i-1] == buf[j+1]

如果这个成立，会使总方案翻倍，因为这个结点既可以是左子树也可以是右子树，而且左子树右子树最下面的并没有影响，每个单儿子结点，都有2种放法，那么一共就是 2^ans 种方法了

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn = 30; char pre[maxn], buf[maxn]; int main() { while(~scanf(" %s %s", pre, buf)) { int ans = 0; for(int i = 0; i < strlen(pre)-1; i++) //因为是pre+1 for(int j = 1; j < strlen(buf); j++) //因为是j-1 if(pre[i] == buf[j] && pre[i+1] == buf[j-1]) ans++; printf("%d\n", 1<<ans); } return 0; }