Solution of Minimum Height Trees

2015-12-13 MoreFreeze 更多博文 » 博客 » GitHub »

原文链接 https://morefreeze.github.io/2015/12/solution-of-minimum-height-trees.html
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。

{% include JB/setup %}

I have trained my algorithm on leetcode a period of time.

Today, I will explain my solution about Minimum Height Trees. My solution beat ~95% against others but it is hard to explain what is I do. Please allow me to introduce the solution from easy to hard. If you only need the last solution, jump to Solution 4.

List of Solutions:

Brute Force Solution

Brute force solution is very easy and direct. Enumerate every node of tree, find the longest path depends on problem description with DFS. {% highlight c++ %} // TLE class BruteForceSolution { public: vector findMinHeightTrees(int n, vector& edges) { VI ans; int min_len(n); if (n <= 0) return ans; if (n == 2) { ans.PB(0); ans.PB(1); return ans; } VI cnt(n); VVI a(n); REP (i, SZ(edges)) { cnt[edges[i].first]++; cnt[edges[i].second]++; a[edges[i].first].PB(edges[i].second); a[edges[i].second].PB(edges[i].first); } REP (i, n) { if (cnt[i] == 0) return ans; if (cnt[i] == 1) continue; map vi; vi[i] = true; int len(0); dfs(i, 0, vi, a, len); if (len <= min_len) { if (len < min_len) ans.clear(); min_len = len; ans.PB(i); } } return ans; } void dfs(int cur, int depth, map &vi, VVI &a, int &len) { len = max(len, depth); REP (i, SZ(a[cur])) { if (!EXIST(vi, a[cur][i])) { vi[ a[cur][i] ] = true; dfs(a[cur][i], depth+1, vi, a, len); vi[ a[cur][i] ] = false; } } } };

{% endhighlight %}

Cut Leaves Solution

Cut leaves of current tree, repeat this process until there are one or two leaves left. {% highlight c++ %} // cut every leaf, again and again, until left one or two node class CutSolution { public: vector findMinHeightTrees(int n, vector& edges) { if (n == 1) { VI ans; ans.PB(0); return ans; } vector > a(n); REP (i, SZ(edges)) { a[edges[i].first].insert(edges[i].second); a[edges[i].second].insert(edges[i].first); } VI ans1, ans2; VI *p1(&ans1), *p2(&ans2); REP (i, SZ(a)) { if (SZ(a[i]) == 1) p1->PB(i); } while (1) { for (auto i: *p1) { for (auto cur : a[i]) { a[ cur ].erase(i); if (SZ(a[ cur ]) == 1) p2->PB(cur); } } if (p2->empty()) return *p1; p1->clear(); swap(p1, p2); } } };

{% endhighlight %}

Find Diameter Solution

Use two DFS to find the diameter and record the diameter path, then pick the middle node what answer is. {% highlight c++ %} // find diameter, then find center // slower than Solution class SolutionDiameter { public: vector findMinHeightTrees(int n, vector& edges) { VVI a(n); REP (i, SZ(edges)) { a[edges[i].first].PB(edges[i].second); a[edges[i].second].PB(edges[i].first); } VI ret(n); VI fa(n); VI p; int diameter(find_diameter(a, ret, fa, p)); VI ans; int cur(p[1]); REP (i, diameter/2) { cur = fa[cur]; } ans.PB(cur); if (diameter%2 == 1) { ans.PB(fa[cur]); } return ans; } // find diameter // ret length from one point // fa father of path // p contain two endpoint // return diameter length int find_diameter(const VVI &a, VI &ret, VI &fa, VI &p) { int diameter; // pick random point to start, so we pick 0, use random can't speed up int point(find_longest(0, a, ret, fa, diameter)); int point2(find_longest(point, a, ret, fa, diameter)); p.PB(point); p.PB(point2); return diameter; } // bfs find longest point int find_longest(int start, const VVI &a, VI &ret, VI &fa, int &diameter) { deque q; q.PB(start); unordered_set v; v.insert(start); ret[start] = 0; while (!q.empty()) { int cur(q.front()); REP (i, SZ(a[cur])) { if (!EXIST(v, a[cur][i])) { v.insert(a[cur][i]); q.PB(a[cur][i]); ret[a[cur][i]] = ret[cur] + 1; fa[a[cur][i]] = cur; } } // the last one of queue if (SZ(q) == 1) { diameter = ret[q.front()]; return q.front(); } q.pop_front(); } return start; } };

{% endhighlight %}

DP-DFS Solution

a[i] convert edges to adjacency list of i

ret[i] the LPL when i as root, so finally we find all smallest ret, that is the answer.

d0[i] the LPL begin with node i through one child of i.

d1[i] the second path length begin with node i through another child of i, if i only have one child, then d1[i] == 0

up_path[i] the path go up through father of i reach one leaf

So, I calculate the d0 and d1 in calc_d, we just travel the tree and get every path length which through child, and assign longest to d0 and second longest to d1

Well, we do many work for this moment, we almost meet our truth.

If we have d0[cur], up_path[cur] as above, the ret[cur] = max(d0[cur], up_path[cur]), is very simple, right? In dfs we will figure out up_path(it will figure out in-place so we don't need array) and ret[cur]. If the path of d0[cur] is in the path of d0[fa](that says they both coincide most partly), up_path will be max(d1[fa], fa_up_path)+1(must compare the other path of father instead of this path contains cur), otherwise, will be max(d0[fa], fa_up_path)+1. Then travel every child do the same thing.

This solution will save tons of time because it don't calculate repeatedly any path twice. DRY. :)

Actually, I wrote four solutions from fastest to slowest. The order of solutions is tree-dp which I explain above, use dfs twice to find the diameter of a tree and record the path, then find the center. The third is cutting the leaves again and again until only one or two node. The lastest is just enumerating every node to find the longest path, then pick the shortest path.

{% highlight c++ %}

include

using namespace std;

//conversion //------------------------------------------ inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math //------------------------------------------- template inline T sqr(T x) {return x*x;}

//typedef //------------------------------------------ typedef vector VI; typedef vector VVI; typedef vector VS; typedef pair PII; typedef long long LL;

//container util //------------------------------------------

define ALL(a) (a).begin(),(a).end()

define RALL(a) (a).rbegin(), (a).rend()

define PB push_back

define MP make_pair

define SZ(a) int((a).size())

define ASZ(a) (a),(a)+int(sizeof(a)/sizeof(a[0]))

define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

define EXIST(s,e) ((s).find(e)!=(s).end())

define SORT(c) sort((c).begin(),(c).end())

//repetition //------------------------------------------

define FOR(i,a,b) for(int i=(a);i<(b);++i)

define REP(i,n) FOR(i,0,n)

//constant //-------------------------------------------- const double EPS = 1e-10; const double PI = acos(-1.0);

//clear memory

define CLR(a) memset((a), 0 ,sizeof(a))

//debug

define dump(x) cerr << #x << " = " << (x) << endl;

define debug(x) cerr << #x << " = " << (x) << " (L" << LINE << ")" << " " << FILE << endl;

// d0 cur node longest path // d1 cur node second longest path without longest path // ret[cur] = max(d0[cur], go up through father longest path) class Solution { public: vector findMinHeightTrees(int n, vector& edges) { VVI a(n); REP (i, SZ(edges)) { a[edges[i].first].PB(edges[i].second); a[edges[i].second].PB(edges[i].first); } VI d0(n), d1(n); calc_d(-1, 0, d0, d1, a); VI ret(n); dfs(-1, 0, 0, d0, d1, a, ret); int min_len(n); REP (i, n) { min_len = min(min_len, ret[i]); } VI ans; REP (i, n) { if (min_len == ret[i]) ans.PB(i); } return ans; } void dfs(int fa, int cur, int fa_up_path, const VI &d0, const VI &d1, const VVI &a, VI &ret) { // go up through father node which longest path int up_path; if (fa == -1) up_path = 0; else if (d0[cur]+1 == d0[fa]) { up_path = max(fa_up_path, d1[fa]) + 1; } // <= else { up_path = max(fa_up_path, d0[fa]) + 1; } ret[cur] = max(d0[cur], up_path); REP (i, SZ(a[cur])) { if (a[cur][i] == fa) continue; dfs(cur, a[cur][i], up_path, d0, d1, a, ret); } } int calc_d(int fa, int cur, VI &d0, VI &d1, const VVI &a) { int l0(0), l1(0); REP (i, SZ(a[cur])) { if (a[cur][i] == fa) continue; int l(calc_d(cur, a[cur][i], d0, d1, a) + 1); if (l > l0) { l1 = l0; l0 = l; } else if (l > l1) { l1 = l; } } d0[cur] = l0; d1[cur] = l1; return l0; } };