题解|树的高度

题目链接

通过广度优先搜索（BFS）来求解树的高度，其核心思想是将“求树的高度”转化为“求根节点到所有其他节点的最大距离”。

#include<stdio.h>
#include<string>
#include<queue>
using namespace std;

int main() {
	int n, m;
	scanf("%d%d", &n, &m);//输入结点个数，根结点编号
	//用邻接表存储边和结点，邻接表的本质是二维数组
	vector<vector<int>>tree(n + 1);//tree[0]不用
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	//广度优先遍历邻接表
	queue<int> toVisit;
	toVisit.push(m);//根入队
	vector<int> distance(n + 1,-1);//初始化所有结点到根的层数为-1
	distance[m] = 0;//根到根层数为0
	int maxdis = 0;
	while (toVisit.empty() == false) {
		int current = toVisit.front();
		toVisit.pop();//队头元素出队
		//访问所有相邻结点
		for (int i= 0; i < tree[current].size(); i++) {
			int child = tree[current][i];
			if (distance[child] != -1) {
				continue;//已访问过则跳过处理
			}
			toVisit.push(child);//未被访问过则加入队列
			distance[child] = distance[current] + 1;//比当前结点远一层
			maxdis = distance[child];//BFS是按层推进的，maxdis最终存储的就是遍历过程中遇到的最大层数
		}

		
	}
	printf("%d\n", maxdis);
	return 0;

}