P4913【深基16.例3】二叉树深度-创新互联

题目描述

有一个 n(n \le 10^6)n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号(均不超过 nn),建立一棵二叉树(根节点的编号为 11),如果是叶子结点,则输入 0 0

10多年的丁青网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整丁青建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联公司从事“丁青网站设计”,“丁青网站推广”以来,每个客户项目都认真落实执行。

建好这棵二叉树之后,请求出它的深度。二叉树的深度是指从根节点到叶子结点时,最多经过了几层。

输入格式

第一行一个整数 nn,表示结点数。

之后 nn 行,第 ii 行两个整数 ll、rr,分别表示结点 ii 的左右子结点编号。若 l=0l=0 则表示无左子结点,r=0r=0 同理。

输出格式

一个整数,表示大结点深度。

输入输出样例

输入 #1复制

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

输出 #1复制

4

1.这道题,去创建二叉树去做的话,是比较麻烦的,用dfs可以。

2.这道题之所以用dfs,是因为他输入的数据适合使用dfs,这个题目的意思一定要搞明白,之前就是搞不明白,然后大眼瞪小眼看了一下午没明白。

这道题说的是  第 i行两个整数 l、r,分别表示结点 i的左右子结点编号。

以下面这道题目为列子:

创建出来的二叉树:

这里是不计算 0 的节点的。所以是很适合使用dfs的。

我们可以先把节点记下来,在一个结构体中。

然后使用 dfs的方式去使用就可以,因为dfs的特点是不撞南墙不回头,当它遇到0时,我们结束即可。从根节点开始递归,分别递归左右子树,即可。

代码如下:(C语言)

#include#define N 1000010
struct node
{
	int l;
	int r;
}a[N];
int max;
int dfs(int x,int step)
{
	if(x==0)
	{
		if(max

c++代码:

#include#includeusing namespace std;

const int N = 1e6 + 10;
struct node 
{
	int l;
	int r;
} a[N];
int maxstep;
int dfs(int x, int step) 
{
	if (x == 0) 
	{
		if (maxstep< step) maxstep = step;
		return 0;
	}
	dfs(a[x].l, step + 1);
	dfs(a[x].r, step + 1);
}

int main() 
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i<= n; i++) 
	{
		cin >>a[i].l >>a[i].r;
	}
	dfs(1, 0);
	cout<< maxstep<< endl;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧

分享名称:P4913【深基16.例3】二叉树深度-创新互联
标题URL:https://www.cdcxhl.com/article32/dsigsc.html

成都网站建设公司_创新互联,为您提供企业网站制作小程序开发网站排名服务器托管网站设计全网营销推广

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联