每日一题-最小高度树

发表于 分类于 Waline：

310. 最小高度树

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-height-trees

题目

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

思路

将这张图想象成一个从中间节点向外延伸的网，该节点到最远处的距离就是最小高度。想办法找出该节点即可，首先找出图中最长的一条路径，例如为A->B，则B节点一定在这条最长路径中，随后再从B节点出发找出最长路径B->C，那么该条路径就是图中的最长路径。

  • 当该路径长度l为奇数，距离B和C点距离均为l/2的节点为满足要求的根节点。
  • 若路径长度l为偶数，记mid=l/2，则mid与mid+1均有可能是满足要求的点

利用三次广度优先搜索寻找最长路径，并记录下路径上各点距离。
也可以记录路径上节点的父节点，只用两次搜索即可完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
	public:
	    int findFarthestNode(unordered_map<int,vector<int>> &map, unordered_map<int,int> &depth, int node, int n) {
		vector<int> visit(n,0);
		visit[node] = 1;
		queue<pair<int,int>> q;
		q.emplace(node,0);
		int maxDepth = 0;
		int farthestNode = node;
		while(!q.empty()) {
			int node = q.front().first;
			int h = q.front().second;
			q.pop();
			depth[node] = h;
			if (h > maxDepth) {
				farthestNode = node;
			}
			for (int nextNode:map[node]) {
				if (visit[nextNode]) {
					continue;
				}
				visit[nextNode] = 1;
				q.emplace(nextNode,h+1);
			}
		}
		return farthestNode;
	}
	vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
		if (n == 1) {
			return {
				0
			}
			;
		}
		// 随便从一点开始
		unordered_map<int,vector<int>> map;
		for (auto &edge:edges) {
			map[edge[0]].push_back(edge[1]);
			map[edge[1]].push_back(edge[0]);
		}
		unordered_map<int,int> depth1;
		unordered_map<int,int> depth2;
		int node1 = findFarthestNode(map,depth1,0,n);
		int node2 = findFarthestNode(map,depth2,node1,n);
		findFarthestNode(map,depth1,node2,n);
		vector<int> ans;
		if (depth2[node2]&1) {
			// // 如果有偶数个节点 应该中点左右两个节点
			int mid = depth2[node2]/2;
			for (auto &it:depth2) {
				if (it.second == mid && depth1[it.first] == mid+1) {
					ans.push_back(it.first);
				}
				if (it.second == mid+1 && depth1[it.first] == mid) {
					ans.push_back(it.first);
				}
			}
		} else {
			// 如果有奇数个节点 符合要求的节点到两边距离应该是一样的
			int mid = depth2[node2]/2;
			for (auto &it:depth2) {
				if (it.second == mid && it.second == depth1[it.first]) {
					ans.push_back(it.first);
				}
			}
		}
		return ans;
	}
}
;