Medium

题目描述

一个王国里有国王、他的孩子们、孙子们等等。偶尔，这个家族中会有人去世或者孩子出生。

王国有一个明确定义的继承顺序，国王是第一个成员。让我们定义递归函数 Successor(x, curOrder)，给定一个人 x 和到目前为止的继承顺序，返回在继承顺序中 x 后面应该是谁。

Successor(x, curOrder):
    if x 没有孩子或者所有 x 的孩子都在 curOrder 中:
        if x 是国王 return null
        else return Successor(x的父亲, curOrder)
    else return x 最年长的不在 curOrder 中的孩子

例如，假设我们有一个由国王、他的孩子 Alice 和 Bob（Alice 比 Bob 年长）以及 Alice 的儿子 Jack 组成的王国。

  • 一开始，curOrder 将是 [“king”]。
  • 调用 Successor(king, curOrder) 将返回 Alice，所以我们将 curOrder 更新为 [“king”, “Alice”]。
  • 调用 Successor(Alice, curOrder) 将返回 Jack，所以我们将 curOrder 更新为 [“king”, “Alice”, “Jack”]。
  • 调用 Successor(Jack, curOrder) 将返回 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() 返回一个列表，表示当前的继承顺序，但不包括死亡的人。

示例 1：

输入：
["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"]]

提示：

  • 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
  • kingName、parentName、childName 和 name 仅由小写英文字母组成。
  • 所有的 childName 和 kingName 参数都是不相同的。
  • death 的所有 name 参数都将首先传递给构造函数或作为 childName 传递给 birth。
  • 对于每次 birth(parentName, childName) 的调用，都保证 parentName 是活着的。
  • 最多有 10^5 次对 birth 和 death 的调用。
  • 最多有 10 次对 getInheritanceOrder 的调用。

解题思路

解题思路

这道题要求我们实现一个王位继承系统。关键在于理解继承规则和数据结构的选择。

继承规则分析： 根据题目描述，继承顺序遵循先序遍历（DFS前序遍历）的规则：

  1. 首先访问当前节点
  2. 然后按照孩子的出生顺序递归访问所有孩子

数据结构设计：

  1. 使用哈希表存储每个人的孩子列表，便于快速添加新生儿
  2. 使用哈希表记录已死亡的人员，便于在获取继承顺序时跳过
  3. 记录国王的名字作为树的根节点

核心算法：

  • birth(): 在父节点的孩子列表中添加新孩子
  • death(): 在死亡集合中标记该人员
  • getInheritanceOrder(): 从国王开始进行DFS前序遍历，跳过已死亡人员

时间复杂度优化： 由于继承顺序本质上是树的前序遍历，我们可以在每次调用getInheritanceOrder()时实时计算，避免维护额外的状态。

这种设计既保证了操作的高效性，又能正确处理动态的出生和死亡事件。

代码实现

class ThroneInheritance {
private:
    string king;
    unordered_map<string, vector<string>> children;
    unordered_set<string> dead;
    
    void dfs(const string& name, vector<string>& result) {
        if (dead.find(name) == dead.end()) {
            result.push_back(name);
        }
        for (const string& child : children[name]) {
            dfs(child, result);
        }
    }
    
public:
    ThroneInheritance(string kingName) {
        king = kingName;
    }
    
    void birth(string parentName, string childName) {
        children[parentName].push_back(childName);
    }
    
    void death(string name) {
        dead.insert(name);
    }
    
    vector<string> getInheritanceOrder() {
        vector<string> result;
        dfs(king, result);
        return result;
    }
};

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.children = defaultdict(list)
        self.dead = set()
    
    def birth(self, parentName: str, childName: str) -> None:
        self.children[parentName].append(childName)

    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        result = []
        
        def dfs(name):
            if name not in self.dead:
                result.append(name)
            for child in self.children[name]:
                dfs(child)
        
        dfs(self.king)
        return result

public class ThroneInheritance {
    private string king;
    private Dictionary<string, List<string>> children;
    private HashSet<string> dead;

    public ThroneInheritance(string kingName) {
        king = kingName;
        children = new Dictionary<string, List<string>>();
        dead = new HashSet<string>();
    }
    
    public void Birth(string parentName, string childName) {
        if (!children.ContainsKey(parentName)) {
            children[parentName] = new List<string>();
        }
        children[parentName].Add(childName);
    }
    
    public void Death(string name) {
        dead.Add(name);
    }
    
    public IList<string> GetInheritanceOrder() {
        List<string> result = new List<string>();
        DFS(king, result);
        return result;
    }
    
    private void DFS(string name, List<string> result) {
        if (!dead.Contains(name)) {
            result.Add(name);
        }
        if (children.ContainsKey(name)) {
            foreach (string child in children[name]) {
                DFS(child, result);
            }
        }
    }
}

var ThroneInheritance = function(kingName) {
    this.king = kingName;
    this.children = new Map();
    this.dead = new Set();
};

ThroneInheritance.prototype.birth = function(parentName, childName) {
    if (!this.children.has(parentName)) {
        this.children.set(parentName, []);
    }
    this.children.get(parentName).push(childName);
};

ThroneInheritance.prototype.death = function(name) {
    this.dead.add(name);
};

ThroneInheritance.prototype.getInheritanceOrder = function() {
    const result = [];
    
    const dfs = (name) => {
        if (!this.dead.has(name)) {
            result.push(name);
        }
        const childList = this.children.get(name) || [];
        for (const child of childList) {
            dfs(child);
        }
    };
    
    dfs(this.king);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(1)O(1)
birth()O(1)O(1)
death()O(1)O(1)
getInheritanceOrder()O(n)O(n)

其中 n 是家族中所有人的总数。getInheritanceOrder() 需要遍历整个家族树，因此时间复杂度为 O(n)。空间复杂度主要来自存储家族关系的数据结构和递归调用栈。

相关题目