How does Throne Inheritance relate to tree traversal patterns?

The problem is fundamentally a DFS traversal over a tree where each node is a family member, ensuring the correct inheritance order recursively.

Do I remove nodes when a family member dies?

No, mark them as deceased in a set. This allows DFS to skip them while keeping child order intact.

Can the inheritance order change after multiple births?

Yes, each birth adds a new child to the parent's node. DFS will traverse them in birth order, reflecting changes correctly.

What data structures are optimal for Throne Inheritance?

Use a tree for parent-child relationships and a hash map for fast name-to-node lookups, along with a set to track deceased members.

How do I efficiently retrieve the inheritance order repeatedly?

Use DFS starting from the king, skipping deceased members. This avoids recalculating the entire tree while maintaining order.

#1600

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

王位继承顺序

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。 Succes…

哈希表树深度优先搜索设计

题目描述

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 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 对应的人员是活着的。
最多调用 10⁵ 次birth 和 death 。
最多调用 10 次 getInheritanceOrder 。

lightbulb

解题思路

方法一：多叉树的前序遍历

根据题目描述，我们可以发现，王位继承顺序实际上是一个多叉树的前序遍历。我们可以使用一个哈希表 $g$ 存储每个人的孩子，使用一个集合 $dead$ 存储已经去世的人。

调用 birth(parentName, childName) 时，我们将 childName 添加到 parentName 的孩子列表中。
调用 death(name) 时，我们将 name 添加到 dead 集合中。
调用 getInheritanceOrder() 时，我们从国王开始进行深度优先搜索，如果当前节点 x 没有去世，我们将 x 添加到答案列表中，然后递归地遍历 x 的所有孩子。

时间复杂度方面，birth 和 death 的时间复杂度均为 $O(1)$ ，getInheritanceOrder 的时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。其中 $n$ 是节点数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.g = defaultdict(list)

    def birth(self, parentName: str, childName: str) -> None:
        self.g[parentName].append(childName)

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

    def getInheritanceOrder(self) -> List[str]:
        def dfs(x: str):
            x not in self.dead and ans.append(x)
            for y in self.g[x]:
                dfs(y)

        ans = []
        dfs(self.king)
        return ans


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

speed

复杂度分析

指标	值
时间	complexity for getInheritanceOrder is O(N) where N is the total number of living descendants, as DFS visits each node once. Birth and death operations are O(1) due to hash map access and set marking. Space complexity is O(N) for storing the tree nodes and live/deceased states.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Clarify whether deaths remove nodes or just mark them.
question_mark
Expect a tree structure that preserves children order for DFS traversal.
question_mark
Ask about efficient retrieval after multiple births and deaths without full recomputation.

warning

常见陷阱

外企场景

error
Forgetting to skip deceased members in DFS leading to incorrect inheritance order.
error
Modifying the tree structure on death instead of using a marker, which complicates updates.
error
Assuming unordered children or using BFS, which breaks the oldest-to-youngest traversal requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Track inheritance with arbitrary parent-to-child ordering instead of oldest-first priority.
arrow_right_alt
Allow multiple kings or parallel family branches requiring merged DFS traversal.
arrow_right_alt
Implement additional queries like 'who is the nth in line' without traversing the full tree.

help

常见问题

外企场景

继续练习

#1261 在受污染的二叉树中查找元素 #1993 树上的操作 #1519 子树中标签相同的节点数