P4913【深基16.例3】二叉树深度-创新互联
题目描述有一个 n(n \le 10^6)n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号(均不超过 nn),建立一棵二叉树(根节点的编号为 11),如果是叶子结点,则输入
10多年的丁青网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整丁青建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联公司从事“丁青网站设计”,“丁青网站推广”以来,每个客户项目都认真落实执行。0 0
。建好这棵二叉树之后,请求出它的深度。二叉树的深度是指从根节点到叶子结点时,最多经过了几层。
输入格式第一行一个整数 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://cdiso.cn/article/dsigsc.html