Description

Submission

class ThroneInheritance {
    struct TreeNode {
        vector<TreeNode*> successors;
        bool alive;
        string name;

        TreeNode(string name)
            :
            name(name),
            alive(true)
            {}
    };
    unordered_map<string, TreeNode*> Map;
    TreeNode* root;
public:
    ThroneInheritance(string kingName) {
        root = new TreeNode(kingName);
        Map[kingName] = root;
    }
    
    void birth(string parentName, string childName) {
        TreeNode* parent = Map[parentName];
        TreeNode* child = new TreeNode(childName);
        Map[childName] = child;
        parent->successors.push_back(child);
    }
    
    void death(string name) {
        Map[name]->alive = false;
    }
    
    vector<string> getInheritanceOrder() {
        // preorder traversal

        vector<string> rets;

        stack<TreeNode*> stk;
        stk.push(root);

        while(!stk.empty()) {
            TreeNode* cur = stk.top();
            stk.pop();
            if(cur->alive) {
                rets.push_back(cur->name);
            }

            for(auto iter = cur->successors.rbegin(); iter != cur->successors.rend(); ++iter) {
                stk.push(*iter);
            }
        }

        return rets;
    }
};

/**
 * 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();
 */