1, Title

  in a kingdom lived the king, his children, his grandchildren and so on. At every point in time, someone in the family is born and someone dies.

  this kingdom has a clearly defined order of succession to the throne, and the first heir is always the king himself. We define the recursive function success (x, curorder). Given a person x and the current inheritance order, the function returns the next successor of X.

Successor(x, curOrder):
If x has no children or all x's children are in curOrder:
If x is the king, null is returned
Otherwise, it returns success (the father of X, curOrder)
Otherwise, the oldest child whose x is not in curOrder is returned

  for example, suppose the kingdom is composed of a king, his children Alice and Bob (Alice is older than Bob) and Alice's child Jack.

     1. in limine, curOrder by ["king"].
     1. call Successor(king, curOrder) ，return Alice ，So we will Alice Put curOrder In, get ["king", "Alice"] . 
     1. call Successor(Alice, curOrder) ，return Jack ，So we will Jack Put curOrder In, get ["king", "Alice", "Jack"] . 
     1. call Successor(Jack, curOrder) ，return Bob ，So we will Bob Put curOrder In, get ["king", "Alice", "Jack", "Bob"] . 
     1. call Successor(Bob, curOrder) ，return null . Finally, the inheritance order is ["king", "Alice", "Jack", "Bob"] . 

  through the above functions, we can always get a unique inheritance order.

   please implement throneiinheritance class:

• Throneiinheritance (string kingname) initializes an object of throneiinheritance class. The name of the king is passed in as an argument to the constructor.
• void birth(string parentName, string childName) means that parentName has a new child named childName.
• void death(string name) indicates that the person named name died. A person's death will not affect the success function, nor will it affect the current inheritance order. You can only mark this person as dead.
• string[] getInheritanceOrder() returns the list of current inheritance order to remove the dead.

Click to view the original question
Difficulty level: medium

2, Train of thought

1) Preorder traversal of multitree

  it is difficult to understand the topic
   generate a multi fork tree according to the meaning of the question. The children of the same parents are in the same List, and the node of death is marked with a HashSet, which is not added to the result when traversing

3, Code

1) Preorder traversal of multitree

class ThroneInheritance {
    private Map<String, List<String>> map;
    private Set<String> deathSet;
    private String kingName;
    public ThroneInheritance(String kingName) {
        map = new HashMap();
        deathSet = new HashSet();
        this.kingName = kingName;
    }
    
    public void birth(String parentName, String childName) {
        if (!map.containsKey(parentName)) {
            map.put(parentName, new ArrayList<String>());
        }
        map.get(parentName).add(childName);
    }
    
    public void death(String name) {
        deathSet.add(name);
    }
    
    public List<String> getInheritanceOrder() {
        List<String> ans = new ArrayList();
        dfs(ans, kingName);
        return ans;
    }

    private void dfs(List<String> ans, String parentName) {
        if (!deathSet.contains(parentName)) {
            ans.add(parentName);
        }
        if (map.containsKey(parentName)) {
            List<String> childs = map.get(parentName);
            for (String child : childs) {
                dfs(ans, child);
            }
        }
    }
}

   time complexity is O(n), space complexity is O(n)