题解 P1229 【遍历问题】

##本题思路： 我们首先可以明确的是，在一棵树上若有一个结点是只有一个子结点的那么这个子结点在左在右不影响先序后序的遍历顺序，那么总树数就要乘以2（乘法原理，这个子结点有两种选择，一种成为左子树，一种成为右子树），为了找到只有一个子结点的结点数，我们继续。。 我们可以得到一个规律，在先序遍历中某一元素A的后继元素B，如果在后序遍历中A的前驱元素是B，那么A只有一个子树，问题即得解 然后为什么呢。。 楼下提醒了我，先序遍历中，如果A只有一个子树B，那么在先序遍历中A一定在B前，在后序遍历中B一定在A前，根据先序遍历和后序遍历的定义和性质可以看出，那么这样想到了的话，实现起来就简单了，大概是###O(n2)可以跑过 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; char a[10002],b[10002];//分别记录前序和后序 int main() { scanf("%s\n%s",&a,&b); int len=strlen(a),ans=1; for(int i=0;i<=len-2;i++) for(int j=0;j<=len-1;j++) if(b[j]==a[i]&&b[j-1]==a[i+1]) ans*=2; cout<<ans; return 0; } ```