Krammer's blog

https://leetcode.com/problems/throne-inheritance/ from Google

Since the contrains say the parentName.length, childName.length, and name.length will be less or equal to 15, the depth of the tree will be less than 16. There will be only at most 10^5 calls of birth and death, so even if we go through all the nodes once for each call, the total time will be only 15*10^5, which is still acceptable in terms of time complexity.

After realizing this, we just need to use a map to represent the edges, and then use another set to store the death names. Then, for each getInheritanceOrder call, we just need to do a dfs from the root and exclude the death names. That’s it. The below is the code I wrote in the context.

 1class ThroneInheritance {
 2public:
 3    unordered_map<string, vector<string>> mp;
 4    unordered_set<string> d;
 5    string k;
 6    
 7    ThroneInheritance(string kingName) {
 8        k = kingName;
 9    }
10    
11    void birth(string parentName, string childName) {
12        mp[parentName].push_back(childName);
13    }
14    
15    void death(string name) {
16        d.insert(name);
17    }
18    
19    void dfs(string cur, vector<string>& ret) {
20        if (d.count(cur) == 0)
21            ret.push_back(cur);
22        for (auto nxt : mp[cur]) {
23            dfs(nxt, ret);
24        }
25    }
26    
27    vector<string> getInheritanceOrder() {
28        vector<string> ret;
29        dfs(k, ret);
30        return ret;
31    }
32};

Editorial: LeetCode 1600 Throne Inheritance