多叉树先序遍历,LeetCode 1600. 王位继承顺序

2024-04-08 18:12

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

目录

一、题目

1、题目描述

2、接口描述

python3

cpp

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

python3

cpp


一、题目

1、题目描述

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

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

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

比方说,假设王国由国王,他的孩子 Alice 和 Bob (Alice 比 Bob 年长)和 Alice 的孩子 Jack 组成。

  1. 一开始, curOrder 为 ["king"].
  2. 调用 Successor(king, curOrder) ,返回 Alice ,所以我们将 Alice 放入 curOrder 中,得到 ["king", "Alice"] 。
  3. 调用 Successor(Alice, curOrder) ,返回 Jack ,所以我们将 Jack 放入 curOrder 中,得到 ["king", "Alice", "Jack"] 。
  4. 调用 Successor(Jack, curOrder) ,返回 Bob ,所以我们将 Bob 放入 curOrder 中,得到 ["king", "Alice", "Jack", "Bob"] 。
  5. 调用 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() 返回 除去 死亡人员的当前继承顺序列表。

2、接口描述

python3
class ThroneInheritance:def __init__(self, kingName: str):def birth(self, parentName: str, childName: str) -> None:def death(self, name: str) -> None:def getInheritanceOrder(self) -> List[str]:# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()
cpp
class ThroneInheritance {
public:ThroneInheritance(string kingName) {}void birth(string parentName, string childName) {}void death(string name) {}vector<string> getInheritanceOrder() {}
};/*** Your ThroneInheritance object will be instantiated and called as such:* ThroneInheritance* obj = new ThroneInheritance(kingName);* obj->birth(parentName,childName);* obj->death(name);* vector<string> param_3 = obj->getInheritanceOrder();*/

3、原题链接

1600. 王位继承顺序 - 力扣(LeetCode)


二、解题报告

1、思路分析

题目显然就是让我们维护一棵树,然后要求能够

  1. 删除树中节点(假删除)
  2. 插入子节点
  3. 返回树的遍历序列,要求按照时间戳先后顺序返回

由于插入子节点已经满足了时间先后,所以对于操作3我们直接返回先序序列即可

对于删除的节点我们放到哈希表里面,遍历的时候我计入答案即可

2、复杂度

时间复杂度:birthO(1)        deadO(1)        构造函数O(1)

查询继承序列O(n)

空间复杂度:O(n)

n为树中节点数目,由于字符串很短所以当作常数未列入复杂度计算

3、代码详解

python3
class ThroneInheritance:def __init__(self, kingName: str):self.king = kingNameself.g = defaultdict(list)self.dead = set()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]:ret = []def dfs(rt: str) -> None:if rt not in self.dead:ret.append(rt)if rt in self.g:for son in self.g[rt]:dfs(son)dfs(self.king)return ret# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()
cpp
class ThroneInheritance {
public:unordered_map<string, vector<string>> g;unordered_set<string> dead;string king;ThroneInheritance(string kingName): king(move(kingName)) {}void birth(string parentName, string childName) {g[move(parentName)].emplace_back(move(childName));}void death(string name) {dead.insert(move(name));}vector<string> getInheritanceOrder() {vector<string> ret;function<void(const string&)> dfs = [&](const string& rt){if(!dead.count(rt))ret.emplace_back(rt);if(g.count(rt))for(const string& son : g[rt])dfs(son);};dfs(king);return ret;}
};/*** Your ThroneInheritance object will be instantiated and called as such:* ThroneInheritance* obj = new ThroneInheritance(kingName);* obj->birth(parentName,childName);* obj->death(name);* vector<string> param_3 = obj->getInheritanceOrder();*/

这篇关于多叉树先序遍历,LeetCode 1600. 王位继承顺序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886224

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹