1600.md

1600. Throne Inheritance

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

# DFS
class ThroneInheritance(object):

    def __init__(self, kingName):
        """
        :type kingName: str
        """
        self.king = kingName
        self.child_dict = {}
        self.child_dict[self.king] = []
        self.is_death = {}
        self.is_death[self.king] = False


    def birth(self, parentName, childName):
        """
        :type parentName: str
        :type childName: str
        :rtype: None
        """
        self.child_dict[parentName].append(childName)
        self.child_dict[childName] = []
        self.is_death[childName] = False


    def death(self, name):
        """
        :type name: str
        :rtype: None
        """
        self.is_death[name] = True


    def getInheritanceOrder(self):
        """
        :rtype: List[str]
        """
        ans = []

        def dfs(cur_person):
            ans.append(cur_person)
            for new_person in self.child_dict[cur_person]:
                dfs(new_person)

        dfs(self.king)

        final_ans = []
        for person in ans:
            if self.is_death[person] == False:
                final_ans.append(person)

        return final_ans



# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()