二叉树的繁茂度

二叉树的繁茂度

时间： 1ms        内存：128M

描述：

一个二叉树的繁茂度定义为各层结点数与树的高度的乘积。 为计算方便树根的高度为0.例如树A(B(D,),C(,)) 的繁茂度为1×0+2×1+1×2=4

输入：

输入有n+1行，第一行为测试数据的组数n. 下面的n行分别为用广义表表示的n棵二叉树，树中的元素用char表示

输出：

输出一共有n行，分别对应n组测试数据，输出此棵树的繁茂度

示例输入：

1
A(B(D,),C(,))

示例输出：

4

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h>
int main()
{
	char a[1000];
	int i,k,s,n,b[1000];
    scanf("%d",&n);
	while(n--)
	{
		s=k=0;
		memset(b,0,sizeof(b));
		scanf("%s",a);
		for(i=0;i<strlen(a);i++)
		{
			if(a[i]!='('&&a[i]!=')'&&a[i]!=',')
				b[k]++;
			else
				if(a[i]=='(')
					k++;
				else
					if(a[i]==')')
						k--;
		}
		for(i=0;a[i]!=0;i++)
			s+=i*b[i];
		printf("%d\n",s);
	} 
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
int main()
{
    char str[1000];
    int i,t,len,deep,sum;
    scanf("%d",&t);
    while(t--)
    {
        sum=deep=0;
        scanf("%s",str);
        len=strlen(str);
        for(i=0;i<len;i++)
        {
            if(str[i]>='A'&&str[i]<='Z')
               sum+=deep;
            else if(str[i]=='(')
                        deep++;
            else if(str[i]==')')
                deep--;
        }
        printf("%d\n",sum);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。