1600.王位继承顺序

链接：1600.王位继承顺序
难度：Medium
标签：树、深度优先搜索、设计、哈希表
简介：一个王国里住着国王、他的孩子们、他的孙子们等等。通过以上的函数，我们总是能得到一个唯一的继承顺序。

题解 1 - python

• 编辑时间：2024-04-07
• 执行用时：333ms
• 内存消耗：68.36MB
• 编程语言：python
• 解法介绍：前序遍历。

class ThroneInheritance:
    def __init__(self, kingName: str):
        self.kingName = 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 successor(self, x: str, curOrder: List[str]) -> List[str]:
        if x not in self.dead: curOrder.append(x)
        for child in self.children[x]:
            self.successor(child, curOrder)
        return curOrder
    def getInheritanceOrder(self) -> List[str]:
        return self.successor(self.kingName, [])

题解 2 - typescript

• 编辑时间：2021-06-20
• 执行用时：188ms
• 内存消耗：43.8MB
• 编程语言：typescript
• 解法介绍：前序遍历。

class Person {
  children: Person[] = [];
  dead = false;
  constructor(public name: string) {}
}
class ThroneInheritance {
  king = new Person('');
  nameMap = new Map<string, Person>();
  constructor(kingName: string) {
    this.king.name = kingName;
    this.nameMap.set(kingName, this.king);
  }
  birth(parentName: string, childName: string): void {
    const parent = this.nameMap.get(parentName)!;
    const child = new Person(childName);
    this.nameMap.set(childName, child);
    parent.children.push(child);
  }
  death(name: string): void {
    this.nameMap.get(name)!.dead = true;
  }
  getInheritanceOrder(): string[] {
    return this._getInheritanceOrder(this.king)
      .filter(v => !v.dead)
      .map(v => v.name);
  }
  private _getInheritanceOrder(person: Person): Person[] {
    const ans: Person[] = [person];
    person.children.forEach(child => {
      ans.push(...this._getInheritanceOrder(child));
    });
    return ans;
  }
}