题解 P1229 【遍历问题】

fl_334 · 2016-11-10 20:28:01 · 题解

前->前序遍历 中->中序遍历 后->后序遍历

思路：给定中能确定树的具体结构，是因为可以确定是左子树还是右子树，而之给定前和后，则不能确定，这就是会出现不同树结构的原因。

只有 前和 后 那么主要问题就是没有办法处理只有一个子树の情况，因为 这种情况 不知道子树 究竟是这个节点的左子树还是右子树，也就是说其实这道题要判断遍历中存在着多少个只有一棵子树的情况。对于前，如果一个结点的下个结点等于后中对应结点的前一个结点的话，那么这个结点就是根节点且其只有一个子树。sum初始化为1，出现一个只有一棵子树的情况，就把sum*2（每次会出现两种不同的情况，分别是出现左子树和出现右子树）。

还是蛮简单的

附AC代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
    char s[255],s1[255];
    scanf("%s",s);
    scanf("%s",s1);
    int len=strlen(s);
    int sum=1,k=0;
    for (int i=0;i<=len-1;i++)
    {
        k=0;
        for (int j=0;j<=len;j++)
        if (s[i]==s1[j]) 
        {
            k=j;    
            break;                                              //找它在后序遍历中出现的位置。ps：c+没pos函数真心不爽
        }
        if ((k!=0)&&(s1[k-1]==s[i+1])) sum<<=1;          //判断成功就sum=sum<<1
    }
    cout<<sum;
}