1600.md

1600. Throne Inheritance

Solution 1 (time O(n), space O(n))

# DFS
class ThroneInheritance {
private:
    unordered_map<string, vector<string>> child_dict;
    unordered_set<string> is_death;
    string king;

public:
    ThroneInheritance(string kingName) {
        king = kingName;
    }
    
    void birth(string parentName, string childName) {
        child_dict[parentName].push_back(childName);
    }
    
    void death(string name) {
        is_death.insert(name);
    }
    
    vector<string> getInheritanceOrder() {
        vector<string> ans;
        dfs(king, ans);
        return ans;   
    }

    void dfs(string name, vector<string>& ans) {
        if (!is_death.count(name)) {
            ans.push_back(name);
        }
        if (child_dict.count(name)) {
            for (int i = 0; i < child_dict[name].size(); i++) {
                dfs(child_dict[name][i], ans);
            }
        }
    }
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance* obj = new ThroneInheritance(kingName);
 * obj->birth(parentName,childName);
 * obj->death(name);
 * vector<string> param_3 = obj->getInheritanceOrder();
 */