多叉树题目：王位继承顺序

本文主要是介绍多叉树题目：王位继承顺序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

标题和出处

标题：王位继承顺序

出处：1600. 王位继承顺序

难度

5 级

题目描述

要求

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

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。定义递归函数 $\text{Successor(x, curOrder)}$，该函数给定一个人 $\text{x}$ 和当前的继承顺序，返回 $\text{x}$ 的下一继承人。

Successor(x, curOrder):如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：如果 x 是国王，那么返回 null否则，返回 Successor(x 的父亲, curOrder)否则，返回 x 不在 curOrder 中最年长的孩子

例如，假设王国由国王、他的孩子 Alice 和 Bob（Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

1. 初始时，$\text{curOrder}$ 为 $\text{["king"]}$。
2. 调用 $\text{Successor(king, curOrder)}$，返回 Alice，所以将 Alice 放入 $\text{curOrder}$ 中，得到 $\text{["king", "Alice"]}$。
3. 调用 $\text{Successor(Alice, curOrder)}$，返回 Jack，所以将 Jack 放入 $\text{curOrder}$ 中，得到 $\text{["king", "Alice", "Jack"]}$。
4. 调用 $\text{Successor(Jack, curOrder)}$，返回 Bob，所以将 Bob 放入 $\text{curOrder}$ 中，得到 $\text{["king", "Alice", "Jack", "Bob"]}$。
5. 调用 $\text{Successor(Bob, curOrder)}$，返回 $\text{null}$。最终得到继承顺序为 $\text{["king", "Alice", "Jack", "Bob"]}$。

使用以上的函数，总是能得到一个唯一的继承顺序。

实现 $\text{ThroneInheritance}$ 类：

• $\text{ThroneInheritance(string kingName)}$ 初始化一个 $\text{ThroneInheritance}$ 类的对象。国王的名字作为构造函数的参数传入。
• $\text{void birth(string parentName, string childName)}$ 表示 $\text{parentName}$ 新拥有了一个名为 $\text{childName}$ 的孩子。
• $\text{void death(string name)}$ 表示名为 $\text{name}$ 的人死亡。一个人的死亡不会影响 $\text{Successor}$ 函数，也不会影响当前的继承顺序。可以只将这个人标记为死亡状态。
• $\text{string[] getInheritanceOrder()}$ 返回除去死亡人员的当前继承顺序列表。

示例

示例 1：

输入：
$\text{["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]}$
$\text{[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]}$
输出：
$\text{[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]}$
解释：
$\text{ThroneInheritance t = new ThroneInheritance("king");}$ // 继承顺序：$\text{king}$
$\text{t.birth("king", "andy");}$ // 继承顺序：$\text{king}>\text{andy}$
$\text{t.birth("king", "bob");}$ // 继承顺序：$\text{king}>\text{andy}>\text{bob}$
$\text{t.birth("king", "catherine");}$ // 继承顺序：$\text{king}>\text{andy}>\text{bob}>\text{catherine}$
$\text{t.birth("andy", "matthew");}$ // 继承顺序：$\text{king}>\text{andy}>\text{matthew}>\text{bob}>\text{catherine}$
$\text{t.birth("bob", "alex");}$ // 继承顺序：$\text{king}>\text{andy}>\text{matthew}>\text{bob}>\text{alex}>\text{catherine}$
$\text{t.birth("bob", "asha");}$ // 继承顺序：$\text{king}>\text{andy}>\text{matthew}>\text{bob}>\text{alex}>\text{asha}>\text{catherine}$
$\text{t.getInheritanceOrder();}$ // 返回 $\text{["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]}$
$\text{t.death("bob");}$ // 继承顺序：$\text{king}>\text{andy}>\text{matthew}>\text{bob}（已经去世）>\text{alex}>\text{asha}>\text{catherine}$
$\text{t.getInheritanceOrder();}$ // 返回 $\text{["king", "andy", "matthew", "alex", "asha", "catherine"]}$

数据范围

• $\text{1}\le \text{kingName.length, parentName.length, childName.length, name.length}\le \text{15}$
• $\text{kingName}$，$\text{parentName}$，$\text{childName}$ 和 $\text{name}$ 仅包含小写英语字母
• 所有的参数 $\text{childName}$ 和 $\text{kingName}$ 互不相同
• 所有传给 $\text{death}$ 函数的参数 $\text{name}$ 都会首先传给构造方法或者 $\text{birth}$ 函数中的 $\text{childName}$ 参数
• 每次调用 $\text{birth(parentName, childName)}$ 时，保证 $\text{parentName}$ 对应的人员是活着的
• 最多调用 ${\text{10}}^{\text{5}}$ 次 $\text{birth}$ 和 $\text{death}$
• 最多调用 $\text{10}$ 次 $\text{getInheritanceOrder}$

解法

思路和算法

将王国中的所有人分别看成结点，则王国中的所有人组成一个多叉树，根结点是国王，相邻结点之间的父结点和子结点关系表示父辈和子辈的关系。

调用 $\text{Successor}$ 函数时，优先考虑当前结点的第一个尚未访问的子结点，如果当前结点没有子结点或者当前结点的子结点都访问结束，则回到当前结点的父结点继续操作，直到所有结点都访问过。

根据上述流程可知，$\text{Successor}$ 函数的实质是多叉树的前序遍历，因此需要维护表示王国的多叉树，并支持出生、死亡和获得继承顺序列表的操作。

维护多叉树的方法有多种。一种方法是使用哈希表存储每个人名和所有孩子表示树结构，使用哈希集合存储活着的人名或者死亡的人名（哈希表存储其中的一类人名，根据哈希表中是否存在人名判断人员是活着还是死亡）；另一种方法是创建多叉树结点类，使用哈希表存储每个人名对应的结点。此处使用后一种方法，具体而言，每个结点存储人名、生死状态以及子结点，每个结点创建时状态默认为活着。

构造方法中，使用 $\text{kingName}$ 创建国王结点，将 $\text{kingName}$ 和国王结点存入哈希表中。国王结点为多叉树的根结点。

对于 $\text{birth}$ 操作，从哈希表中获得 $\text{parentName}$ 对应的父辈结点，使用 $\text{childName}$ 创建子辈结点，将子辈结点加入父辈结点的子结点中，将 $\text{childName}$ 和子辈结点存入哈希表中。

对于 $\text{death}$ 操作，从哈希表中获得 $\text{name}$ 对应的结点，将该结点的状态设为死亡。

对于 $\text{getInheritanceOrder}$ 操作，从国王结点开始前序遍历多叉树。遍历过程中需要访问所有的结点，但是只将状态为活着的结点的名字加入继承顺序列表中。

代码

class ThroneInheritance {private class Node {private String name;private boolean alive;private List<Node> children;public Node(String name) {this.name = name;this.alive = true;this.children = new ArrayList<Node>();}public String getName() {return name;}public boolean isAlive() {return alive;}public void death() {alive = false;}public List<Node> getChildren() {return children;}public Node birth(String name) {Node child = new Node(name);children.add(child);return child;}}private Node king;private Map<String, Node> nodeMap;public ThroneInheritance(String kingName) {king = new Node(kingName);nodeMap = new HashMap<String, Node>();nodeMap.put(kingName, king);}public void birth(String parentName, String childName) {Node parent = nodeMap.get(parentName);Node child = parent.birth(childName);nodeMap.put(childName, child);}public void death(String name) {Node node = nodeMap.get(name);node.death();}public List<String> getInheritanceOrder() {List<String> inheritanceOrder = new ArrayList<String>();preorder(king, inheritanceOrder);return inheritanceOrder;}private void preorder(Node node, List<String> inheritanceOrder) {if (node.isAlive()) {inheritanceOrder.add(node.getName());}List<Node> children = node.getChildren();for (Node child : children) {preorder(child, inheritanceOrder);}}
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(1)$，方法 $\text{birth}$ 的时间复杂度是 $O(1)$，方法 $\text{death}$ 的时间复杂度是 $O(1)$，方法 $\text{getInheritanceOrder}$ 的时间复杂度是 $O(n)$，其中 $n$ 是王国中的人数。构造方法、方法 $\text{birth}$ 和方法 $\text{death}$ 都是常数时间的操作，方法 $\text{getInheritanceOrder}$ 需要 $O(n)$ 的时间前序遍历多叉树。这里将字符串操作的时间视为 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是王国中的人数。存储多叉树和哈希表都需要 $O(n)$ 的空间。这里将字符串占用的空间视为 $O(1)$。

这篇关于多叉树题目：王位继承顺序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---