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】二叉树深度-创新互联
新闻来源:http://ybzwz.com/article/dsigsc.html