題目

一個王國里住著國王、他的孩子們、他的孫子們等等。每一個時間點，這個家庭里有人出生也有人死亡。

這個王國有一個明確規定的皇位繼承順序，第一繼承人總是國王自己。我們定義遞歸函數?Successor(x, curOrder)?，給定一個人?x?和當前的繼承順序，該函數返回 x?的下一繼承人。

Successor(x, curOrder):如果 x 沒有孩子或者所有 x 的孩子都在 curOrder 中：如果 x 是國王，那么返回 null否則，返回 Successor(x 的父親, curOrder)否則，返回 x 不在 curOrder 中最年長的孩子
比方說，假設王國由國王，他的孩子?Alice 和 Bob （Alice 比 Bob?年長）和 Alice 的孩子?Jack 組成。

一開始，?curOrder?為?[“king”].
調用?Successor(king, curOrder)?，返回 Alice ，所以我們將 Alice 放入 curOrder?中，得到?[“king”, “Alice”]?。
調用?Successor(Alice, curOrder)?，返回 Jack ，所以我們將 Jack 放入?curOrder?中，得到?[“king”, “Alice”, “Jack”]?。
調用?Successor(Jack, curOrder)?，返回 Bob ，所以我們將 Bob 放入?curOrder?中，得到?[“king”, “Alice”, “Jack”, “Bob”]?。
調用?Successor(Bob, curOrder)?，返回?null?。最終得到繼承順序為?[“king”, “Alice”, “Jack”, “Bob”]?。
通過以上的函數，我們總是能得到一個唯一的繼承順序。

請你實現?ThroneInheritance?類：

• ThroneInheritance(string kingName) 初始化一個?ThroneInheritance?類的對象。國王的名字作為構造函數的參數傳入。
• void birth(string parentName, string childName)?表示?parentName?新擁有了一個名為?childName?的孩子。
• void death(string name)?表示名為?name?的人死亡。一個人的死亡不會影響?Successor?函數，也不會影響當前的繼承順序。你可以只將這個人標記為死亡狀態。
• string[] getInheritanceOrder()?返回 除去?死亡人員的當前繼承順序列表。

示例：

輸入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
輸出：
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]解釋：
ThroneInheritance t= new ThroneInheritance("king"); // 繼承順序：king
t.birth("king", "andy"); // 繼承順序：king > andy
t.birth("king", "bob"); // 繼承順序：king > andy > bob
t.birth("king", "catherine"); // 繼承順序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 繼承順序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 繼承順序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 繼承順序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // 繼承順序：king > andy > matthew > bob（已經去世）> alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]

提示：

• 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
• kingName，parentName，?childName?和?name?僅包含小寫英文字母。
• 所有的參數?childName 和?kingName?互不相同。
• 所有?death?函數中的死亡名字 name?要么是國王，要么是已經出生了的人員名字。
• 每次調用 birth(parentName, childName) 時，測試用例都保證 parentName 對應的人員是活著的。
• 最多調用?105?次birth 和?death?。
• 最多調用?10?次?getInheritanceOrder?。

解題思路

通過map和list組合，key記錄人名，value記錄孩子名字，這樣就構造出一個具有層級結構的表示繼承關系的多層樹，根節點是國王，因為list的遍歷次序就是插入次序，因此使用深度優先搜索遍歷的順序，就是繼承關系。使用set維護去世的人名，避免加入到結果中去。

代碼

    class ThroneInheritance {Map<String,List<String>> map=new HashMap<>();Set<String> death=new HashSet<>();String king;public ThroneInheritance(String kingName) {king=kingName;map.put(kingName,new ArrayList<>());}public void birth(String parentName, String childName) {if(!map.containsKey(parentName))map.put(parentName,new ArrayList<>());map.get(parentName).add(childName);}public void death(String name) {death.add(name);}public void dfs(List<String> res,String cur){if(!death.contains(cur)) res.add(cur);if(map.containsKey(cur)){for (String s : map.get(cur)) {dfs(res,s);}}}public List<String> getInheritanceOrder() {ArrayList<String> res = new ArrayList<>();dfs(res,king);return res;}}
/*** Your ThroneInheritance object will be instantiated and called as such:* ThroneInheritance obj = new ThroneInheritance(kingName);* obj.birth(parentName,childName);* obj.death(name);* List<String> param_3 = obj.getInheritanceOrder();*/