LeetCode 1600: Throne Inheritance

Explanation:

To solve this problem, we can use a combination of a tree structure to represent the relationships in the kingdom and a list to maintain the order of inheritance excluding dead people.

1. Data Structures:

   • We can represent the relationships in the kingdom using a tree structure where each person is a node with their children as their descendants.
   • We can maintain the order of inheritance using a list where we append the names of people in the order they are born.

2. Algorithm:

   • Initialize the tree with the king as the root node and an empty list for the inheritance order.
   • Implement the birth function to add a child to a parent in the tree.
   • Implement the death function to mark a person as dead in the tree.
   • Implement the getInheritanceOrder function to return the current order of inheritance excluding dead people based on a preorder traversal of the tree.

3. Time Complexity:

   • Initializing the kingdom: O(1)
   • Adding a child: O(1)
   • Marking a person as dead: O(1)
   • Returning the inheritance order: O(n) where n is the number of living people in the kingdom

4. Space Complexity:

   • Storing the relationships in the tree: O(n)
   • Storing the order of inheritance: O(n)

:

class ThroneInheritance {
    Map<String, List<String>> tree;
    Set<String> dead;
    String king;

    public ThroneInheritance(String kingName) {
        tree = new HashMap<>();
        dead = new HashSet<>();
        king = kingName;
        tree.put(king, new ArrayList<>());
    }

    public void birth(String parentName, String childName) {
        tree.get(parentName).add(childName);
        tree.put(childName, new ArrayList<>());
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        dfs(king, order);
        return order;
    }

    private void dfs(String person, List<String> order) {
        if (!dead.contains(person)) {
            order.add(person);
        }
        for (String child : tree.get(person)) {
            dfs(child, order);
        }
    }
}