SCAU18923--二叉树的直径

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 <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>using namespace std;int n; // 节点总数
vector<int> lch(10001); // 存储每个节点的左孩子，索引代表父节点，值代表左孩子节点编号
vector<int> rch(10001); // 存储每个节点的右孩子，索引代表父节点，值代表右孩子节点编号
vector<int> v(10001);   // 记录每个节点作为父节点的出现次数，用于判断左右孩子
int D = 0;              // 记录当前找到的最大直径// 递归函数：返回以 u 为根的子树高度，同时更新直径 D
int dfs(int u) {if (u == 0) {       // 如果当前节点为空（0表示空节点），返回高度0return 0;}int rlen, llen;     // 分别记录左右子树的高度llen = dfs(lch[u]); // 递归计算左子树的高度rlen = dfs(rch[u]); // 递归计算右子树的高度D = max(D, rlen + llen); // 更新最大直径，当前节点的直径是左右子树高度之和return max(rlen, llen) + 1; // 返回当前子树的高度（左右子树中的较大高度 + 1）
}int main() {ios::sync_with_stdio(false); // 关闭同步，提高输入输出速度cin.tie(nullptr);           // 解除cin和cout的绑定，进一步提升速度cin >> n; // 读取节点总数// 读取n-1条边，构建二叉树结构for (int i = 1; i < n; i++) {int m, j;cin >> m >> j; // 读取父节点m和子节点jif (v[m] == 0) {  // 如果m第一次作为父节点出现，j作为左孩子lch[m] = j;} else {           // 否则，j作为右孩子rch[m] = j;}v[m]++; // 增加m作为父节点的出现次数}dfs(1);    // 从根节点（假设为1）开始深度优先搜索，计算子树高度并更新直径Dcout << D; // 输出最大直径return 0;
}