[LeetCode]Minimum Height Trees

一道需要我们事先做一些分析的题目，一个图中可能有多少这样的节点，可以使以其为根节点的时候深度最小。事实上，这样的节点只可能在最长的路径上，并且一定是最中间的一个或者两个节点。假设tree中最长的路径p长度为d，那么我们取中点为root的时候整个tree的最大的深度就是d/2, 因为假设有其他的点c深度超过d/2，那么把p的一半和root再与c相连，整个长度肯定是大于d的，这和我们的假设矛盾。假设有其他不在p上的点n可以在其当root的时候使整个tree的深度小于d/2，那么既然n不在p上，那么因为从p的两头到点n肯定分别只有一条路径（否则会有环），并且共同经过p上的某个节点，那么p的两个端节点，深度是不可能小于d/2的，我们得到了矛盾的结论。所以假设成立，那么找tree中最长的路径，我们可以用DFS或者BFS，DFS的话，我们从任意节点开始，找到某个叶节点，然后从叶节点DFS找到最长路径，然后去其中点即可，假设我们总共有N个节点，那么有N-1条边（N个节点connected至少需要N-1条边，大于N-1条边会产生环），建图和DFS都是O(N)，所以总的时间复杂度就是O(N),代码如下：

	class Solution {
	public:
	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
	if(n <= 0)return {};
	vector<vector<int>> g(n, vector<int>());
	for(auto e : edges)
	{
	g[e.first].push_back(e.second);
	g[e.second].push_back(e.first);
	}
	vector<int> longest, curr;
	longestPath(g, -1, 0, curr, longest);
	int end = longest[longest.size() - 1];
	longest = vector<int>();
	longestPath(g, -1, end, curr, longest);
	vector<int> res;
	res.push_back(longest[(longest.size() - 1) / 2]);
	if (!(longest.size() % 2))res.push_back(longest[(longest.size() - 1) / 2 + 1]);
	return res;
	}
	private:
	void longestPath(vector<vector<int>>& g, int from, int to, vector<int>& curr, vector<int>& longest)
	{
	curr.push_back(to);
	for(auto v : g[to])
	{
	if(v != from)longestPath(g, to, v, curr, longest);
	}
	if(curr.size() > longest.size())longest = curr;
	curr.pop_back();
	}
	};

view raw Minimum Height Trees2.cpp hosted with ❤ by GitHub

BFS的话，我们就类似剥洋葱，从外部的叶节点开始向里面一层一层的删除，知道最后剩下的一个或者两个节点，就是最长路径上的中点，时间复杂度O(N), 代码如下：

	class Solution {
	public:
	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
	unordered_map<int, vector<int>> g;
	unordered_map<int, int> degrees;
	for(auto& e : edges)
	{
	g[e.first].emplace_back(e.second);
	g[e.second].emplace_back(e.first);
	++degrees[e.first];
	++degrees[e.second];
	}
	//collect leaves
	queue<int> leaves;
	for(int i = 0; i < n; ++i)
	if(degrees[i] <= 1)//single node has 0 degree
	leaves.push(i);
	//peel onion
	while(n > 2)
	{
	int len = leaves.size();
	for(int i = 0; i < len; ++i)
	{
	int leave = leaves.front();
	leaves.pop();
	for(auto adj : g[leave])
	if(--degrees[adj] == 1)
	leaves.push(adj);
	}
	n -= len;
	}
	vector<int> res;
	while(leaves.size())
	{
	res.emplace_back(leaves.front());
	leaves.pop();
	}
	return res;
	}
	};

view raw Minimum Height Trees.cpp hosted with ❤ by GitHub