51nod1832 先序遍历与后序遍历

对于给定的一个二叉树的先序遍历和后序遍历，输出有多少种满足条件的二叉树。
两棵二叉树不同当且仅当对于某个x，x的左儿子编号不同或x的右儿子编号不同。

Input

第一行一个正整数n(3<=n<=10000)，表示二叉树的节点数，节点从1到n标号。

第二行n个整数a[i](1<=a[i]<=n)，表示二叉树的先序遍历。

第三行n个整数b[i](1<=b[i]<=n)，表示二叉树的后序遍历。

Output

输出一个整数表示有多少种方案。保证至少有1种方案。

Input示例

Output示例

统计出所有的可能（dfs遍历一次足矣），直接按照二叉树的性质，不过有个大数的运算

#include <stdio.h>

#include <string.h>

int pre[];

int post[];

int cc;

void calc(int a1,int b1,int a2,int b2)

{

    int i;

    if(a1>=b1)  return;

    for(i=a2; i<=b2-; i++)

    {

        if(pre[a1+] == post[i])  break;

    }

    if(i == b2-)  cc++;

    calc(a1+,a1++(i-a2),a2,i);

    calc(a1++(i-a2)+,b1,i+,b2-);

}

int a[];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=; i<n; i++)

        scanf("%d",&pre[i]);

    for(int i=; i<n; i++)

        scanf("%d",&post[i]);

    cc=;

    calc(,n-,,n-);

    n=cc;

    int sum=,i,k;

    for(i=; i<; i++)

        a[i]=;

    a[]=;

    for(k=; k<=n; k++)

    {

        for(i=; i<sum; i++)

            a[i]=a[i]*;

        for(i=; i<sum; i++)

            if(a[i]>=)

            {

                a[i+]=a[i+]+a[i]/;

                if(i+==sum)sum++;

                a[i]=a[i]%;

            }

    }

    for(i=sum-; i>=; i--)

        printf("%d",a[i]);

    printf("\n");

return ;

}

巴特西

51nod1832 先序遍历与后序遍历

最新文章

热门文章