18923 二叉树的直径

本文主要是介绍18923 二叉树的直径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

18923 二叉树的直径
时间限制:1000MS  代码长度限制:10KB
提交次数:0 通过次数:0题型: 编程题   语言: G++;GCC
Description
给定一棵二叉树，你需要计算它的直径长度。
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。1/ \2   3/ \     4   5   
答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n。
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。
x第一次出现时y为左孩子输出格式
输出二叉树的直径。输入样例
5
1 2
1 3
2 4
2 5输出样例
3

求二叉树的直径即求每一个节点构成的树的左右子树层数和的最大值
通过先序遍历求每一棵树的直径。

#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;struct node
{int l=0,r=0;//左右孩子int f=0;//父亲
};
node a[1005],b[1005]= {0};
int sum=0;
int dfs(int i,int temp)//计算层数
{if (a[i].l==0&&a[i].r==0){return 0;}int x=0,y=0;x=dfs(a[i].l,temp)+1;y=dfs(a[i].r,temp)+1;temp=max(x,y)+temp;
//    printf ("i=%d a[i].l=%d a[i].r=%d x=%d y=%d sum=%d\n",i,a[i].l,a[i].r,x,y,temp);return temp;
}void bianli(int t)//先序遍历，求当前子树的最大直径
{int temp=0,x,y;if(a[t].l){x=dfs(a[t].l,0);
//        printf ("(1):%d\n",x);temp=x+1;}if (a[t].r){y=dfs(a[t].r,0);
//        printf ("(2):%d\n",y);temp+=y+1;}sum=max(temp,sum);if (a[t].l)bianli(a[t].l);if (a[t].r)bianli(a[t].r);
//    printf ("sum=%d\n",sum);
}int main()
{int i,j,x,y,n,t=0;scanf("%d",&n);for (i=1; i<n; i++) //读入数据{scanf("%d %d",&x,&y);if (i==1){t=x;//记录树根的位置}if (a[x].l==0){a[x].l=y;a[y].f=x;}else{a[x].r=y;a[y].f=x;}}bianli(t);printf ("%d",sum);return 0;
}

这篇关于18923 二叉树的直径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---