My c++ code beat 95% in minimum height tree


  • -3
    M
    #include <unordered_set>
    #include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cctype>
    #include <string>
    #include <cstring>
    #include <ctime>
    
    using namespace std;
    
    //conversion
    //------------------------------------------
    inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
    template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
    
    //math
    //-------------------------------------------
    template<class T> inline T sqr(T x) {return x*x;}
    
    //typedef
    //------------------------------------------
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<string> VS;
    typedef pair<int, int> 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 through some child
    // d1 cur node second longest path through another child
    // ret[cur] = max(d0[cur], go up through father longest path)
    class Solution {
        public:
            vector<int> findMinHeightTrees(int n, vector<PII>& 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;
            }
    };
    

    My solution is very easy(but not to implement easily).

    In brute force solution, we need calculate the longest path length(LPL) for every node as root, but we know many path we re-calculate. If we can reuse this path, we can figure out all LPL in one tree. For all cases, I pick node 0 as root.

    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.


  • 0
    P

    Your code is so ugly! So difficult to read.


  • 0
    M

    @psc0606 I add my explain above, read again, thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.