18923 二叉树的直径

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 
# include 
//二叉树节点结构体
typedef struct bitree
{int lch;int rch;int parent;
} BiTree;int maxlen;//最大直径，深搜时维护一个最大长度即可
int flag[100005];//标记是否走过当前节点
BiTree a[100005];//构造二叉树编码表，静态存储结构，0号单元不存储数据//深度搜索
void dfs(int cur, int len)
{maxlen = maxlen > len ? maxlen : len;//维护一个最大长度int lch = a[cur].lch, rch = a[cur].rch, parent = a[cur].parent;//cur节点的左孩子、右孩子、父亲if (lch != 0 && flag[lch] == 0)//如果当前节点有左孩子并且没有走过，则深搜左孩子{flag[lch] = 1;dfs(lch, len+1);}if (rch != 0 && flag[rch] == 0)//如果当前节点有右孩子并且没有走过，则深搜右孩子{flag[rch] = 1;dfs(rch, len+1);}if (parent != 0 && flag[parent] == 0)//如果当前节点有父亲并且没有走过，则深搜父亲{flag[parent] = 1;dfs(parent, len+1);}return;
}int main()
{int n, i, q, p;scanf("%d", &n);for (i = 0; i < n-1; i++)//输入n-1个数据{scanf("%d%d", &p, &q);//读入父亲和孩子if (a[p].lch == 0)//如果是左孩子a[p].lch = q;else//如果是右孩子a[p].rch = q;a[q].parent = p;//父亲}maxlen = 1e-9;//查找最大长度，此处初始化maxlen为1e-9for(i = 1; i <= n; i++)//遍历二叉树的每个节点，并对每个节点进行深搜{if (a[i].lch == 0 && a[i].rch == 0)//最大直径，仅需从叶子节点开始深搜{memset(flag,0,sizeof(flag));//注意每次深搜前需要初始化标记数组flag[i] = 1;//当前节点走过dfs(i, 0);//对当前节点进行深搜}}printf("%d\n", maxlen);//输出最大长度return 0;
}

代码简洁版：

#include 
#include 
#include 
using namespace std;typedef struct BiTNode
{int data;int lchild, rchild, parent;
} BiTNode;BiTNode T[1000] = {0};
int v[1000] = {0};//标记数组
int max_step = 0;//存储直径void dfs(int index, int step)
{max_step = max_step > step ? max_step : step;//维护一个最大步数，即直径int lchild = T[index].lchild;//左孩子下标int rchild = T[index].rchild;//右孩子下标int parent = T[index].parent;//父亲下标if (lchild && v[lchild] == 0)//如果有左孩子，则先标记左孩子访问过，再对左孩子深搜{v[lchild] = 1;dfs(lchild,step+1);}if (rchild && v[rchild] == 0)//如果有右孩子，则先标记右孩子访问过，再对右孩子深搜{v[rchild] = 1;dfs(rchild,step+1);}if (parent && v[parent] == 0)//如果有父亲，则先标记父亲访问过，再对父亲深搜{v[parent] = 1;dfs(parent,step+1);}
}int main()
{int n, x, y;cin>>n;for (int i = 1; i < n; i++){cin>>x>>y;if (T[x].lchild == 0)T[x].lchild = y;elseT[x].rchild = y;T[y].parent = x;}for (int i= 0; i < n; i++)if (T[i].lchild == 0 && T[i].rchild == 0){memset(v,0,sizeof(v));v[i] = 1;dfs(i, 0);}cout<<max_step<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！