二叉树的深度

二叉树的深度

时间: 1ms        内存:128M

描述:

给定一个有根二叉树,规定连接两个节点的每条边长度是1,定义树的深度为根到叶子节点距离的最大值。

输入:

第一行是整数n(0 < n <= 10000)节点用1...n表示,接下来有n行,分别表示节点1...n的孩子的情况
每一行有个整数lc, rc,分别表示结点i的左右儿子,为0表示,该孩子为空。

输出:

输出一行,一个整数,为树的深度.

示例输入:

3
2 3
0 0
0 0 

示例输出:

2

提示:

参考答案(内存最优[748]):

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100
int n,l,r;

typedef struct node
{
	int data,lchild,rchild;
}btree;
btree t[MAX];

void create()
{
	int i,lc,rc;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&lc,&rc);
		t[i].data=i;
		t[i].lchild=lc;
		t[i].rchild=rc;
	}
}

int dfs(int i)
{
	if(t[i].data==0)
		return 0;
	if(t[i].lchild==0&&t[i].rchild==0)
		return 1;
	else
	{
		l=dfs(t[i].lchild);
		r=dfs(t[i].rchild);
		if(l>r)
			return l+1;
		else
			return r+1;
	}
}

int main()
{
	memset(t,0,sizeof(t));
	create();
	printf("%d\n",dfs(1));
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100
int n,l,r;

typedef struct node
{
	int data,lchild,rchild;
}btree;
btree t[MAX];

void create()
{
	int i,lc,rc;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&lc,&rc);
		t[i].data=i;
		t[i].lchild=lc;
		t[i].rchild=rc;
	}
}

int dfs(int i)
{
	if(t[i].data==0)
		return 0;
	if(t[i].lchild==0&&t[i].rchild==0)
		return 1;
	else
	{
		l=dfs(t[i].lchild);
		r=dfs(t[i].rchild);
		if(l>r)
			return l+1;
		else
			return r+1;
	}
}

int main()
{
	memset(t,0,sizeof(t));
	create();
	printf("%d\n",dfs(1));
	return 0;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注