codevs 1814 最长链

1814 最长链

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

现给出一棵N个结点二叉树,问这棵二叉树中最长链的长度为多少,保证了1号结点为二叉树的根。

输入描述 Input Description

输入的第1行为包含了一个正整数N,为这棵二叉树的结点数,结点标号由1至N。

接下来N行,这N行中的第i行包含两个正整数l[i], r[i],表示了结点i的左儿子与右儿子编号。如果l[i]为0,表示结点i没有左儿子,同样地,如果r[i]为0则表示没有右儿子。

输出描述 Output Description

输出包括1个正整数,为这棵二叉树的最长链长度。

样例输入 Sample Input

5

2 3

4 5

0 6

0 0

0 0

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

【样例说明】

  4-2-1-3-6为这棵二叉树中的一条最长链。

【数据规模】

对于10%的数据,有N≤10;

对于40%的数据,有N≤100;

对于50%的数据,有N≤1000;

对于60%的数据,有N≤10000;

对于100%的数据,有N≤100000,且保证了树的深度不超过32768。

【提示】

关于二叉树:

二叉树的递归定义:二叉树要么为空,要么由根结点,左子树,右子树组成。左子树和右子树分别是一棵二叉树。

请注意,有根树和二叉树的三个主要差别:

1. 树的结点个数至少为1,而二叉树的结点个数可以为0;

2. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;

3. 树的结点无左、右之分,而二叉树的结点有左、右之分。

关于最长链:

最长链为这棵二叉树中一条最长的简单路径,即不经过重复结点的一条路径。可以容易证明,二叉树中最长链的起始、结束结点均为叶子结点。

分类标签 Tags 点此展开

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,i,ans,a[100000][3],c[100000];
 5 void dfs(int x)
 6 {   
 7     int l=a[x][1],r=a[x][2];
 8 if (a[x][1]!=0) dfs(l);
 9 if (a[x][2]!=0) dfs(r);
10 c[x]=max(c[l],c[r])+1;
11 ans=max(c[l]+c[r]+1,ans);
12 }
13 int main()
14 {
15 scanf("%d",&n);
16 for (i=1;i<=n;i++)
17 scanf("%d%d",&a[i][1],&a[i][2]);
18 dfs(1);
19 printf("%d",ans-1);
20 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏haifeiWu与他朋友们的专栏

聊聊ArrayList源码(基于JDK1.8)

打个广告,楼主自己造的轮子,感兴趣的请点[github]: https://github.com/haifeiWu/lightconf

15140
来自专栏desperate633

ArrayList实现原理分析(Java源码剖析)ArrayList使用的存储的数据结构ArrayList的初始化ArrayList是如何动态增长ArrayList如何实现元素的移除ArrayList

ArrayList是我们经常使用的一个数据结构,我们通常把其用作一个可变长度的动态数组使用,大部分时候,可以替代数组的作用,我们不用事先设定ArrayList的...

14430
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

16010
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

10920
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

29640
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

11830
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

20520
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

23490
来自专栏mathor

LeetCode222. 完全二叉树的节点个数

 常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子...

16230
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

37360

扫码关注云+社区

领取腾讯云代金券