一、简答题
1、1.模拟树遍历
二叉树的中序遍历可以借助一个堆栈来用非递归的方式实现。例如，对一棵有 6 个结点的二叉树（结点键值从 1 到 6）进行遍历，堆栈操作为：push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop() —— 其中 push 为入栈，pop 为出栈。则这套操作对应了一棵唯一的二叉树，如下图所示。
你的任务是输出这棵树的后序遍历序列。
时间限制：1000
内存限制：262144
输入
输入第一行给出一个正整数 N（≤ 30），是二叉树中结点的个数（结点键值从 1 到 N）。随后 2N 行，每行给出一个堆栈操作：`Push X` 表示将键值为 `X` 的结点入栈，`Pop` 表示将一个结点出栈。
输出
在一行中输出该树后序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。裁判保证输入数据一定对应了一棵树。
样例输入
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
样例输出
3 4 2 6 5 1
解析：
根据题目描述，给定的堆栈操作序列对应了一棵二叉树。要得到这棵树的后序遍历序列，我们可以使用非递归的方式进行模拟。
首先，根据输入的堆栈操作序列，我们可以模拟整个二叉树的构建过程。在模拟过程中，可以使用一个堆栈来辅助处理。具体步骤如下：
- 创建一个空堆栈。
- 按照输入的堆栈操作序列进行模拟：
- 遇到 “Push X” 操作，将键值为 X 的结点入栈。
- 遇到 “Pop” 操作，执行出栈操作，并处理出栈的结点：
- 如果该结点的右子树已经处理完毕（即右子结点已经出栈），并且左子树也处理完毕（左子结点已出栈或不存在），那么该结点就是后序遍历的当前结点，将其加入结果序列。
- 否则，将该结点重新入栈，等待后续处理。
- 当所有堆栈操作处理完毕后，如果堆栈中还有剩余的结点，依次弹出并加入结果序列，这些结点是后序遍历的最后一个结点。
根据给定的样例输入，我们可以模拟整个过程并得到后序遍历序列为 3 4 2 6 5 1。
2、2.寻宝图
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。
时间限制：1000
内存限制：262144
输入
输入第一行给出 2 个正整数 N 和 M（1 < N × M ≤ 105），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 `0` 表示水域，`1` 表示陆地，`2`-`9` 表示宝藏。 注意：两个格子共享一条边时，才是“相邻”的。默认地图外围全是水域。
输出
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。
样例输入
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
样例输出
7 2
解析：
{针对这个问题，我们可以使用深度优先搜索（DFS）算法来解决。首先，我们需要读取地图的尺寸和具体的格子数据。然后，我们可以初始化两个计数器，一个用于统计岛屿的总数量，另一个用于统计有宝藏的岛屿的数量。
接下来，我们遍历整个地图。对于每一个陆地格子，我们进行深度优先搜索。在搜索的过程中，我们将遇到的每一个陆地格子都标记为已访问过，以避免重复搜索。如果我们在搜索的过程中遇到了水域或者已经访问过的格子，我们就停止搜索。每次搜索完毕，岛屿数量加一。
同时，在搜索的过程中，我们需要检查这个岛屿上是否有宝藏。如果有宝藏，有宝藏的岛屿数量也加一。
最后，我们输出岛屿的总数量和有宝藏的岛屿的数量。
根据题目的要求，我们需要特别注意地图的边缘都是水域，因此在搜索的过程中需要注意边界条件。另外，由于题目的数据规模较大，我们还需要注意算法的效率，确保能够在规定的时间内完成任务。}
3、3.小字辈
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
时间限制：1000
内存限制：262144
输入
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
样例输入
9
2 6 5 5 -1 5 6 4 7
样例输出
4
1 9
解析：
上述代码通过深度优先搜索找到了家谱中最小的辈分以及该辈分下的所有成员编号，并按照题目要求输出了结果。代码首先创建了一个哈希表来记录每个成员的编号和对应的辈分，然后遍历每个成员进行深度优先搜索。在搜索过程中，更新了每个成员的辈分并记录了最小辈分的成员编号。最后，按照辈分和编号的顺序输出了结果。
4、4.堆中的路径
将一系列给定数字插入一个初始为空的小顶堆`H[]`。随后对任意给定的下标`i`，打印从`H[i]`到根结点的路径。
时间限制：1000
内存限制：262144
输入
每组测试第1行包含2个正整数N和M(≤ 1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出
对输入中给出的每个下标`i`，在一行中输出从`H[i]`到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
样例输入
5 3
46 23 26 24 10
5 4 3
样例输出
24 23 10
46 23 10
26 10
解析：
这个问题可以分为几个步骤来解决：
步骤一：构建小顶堆。根据输入的整数序列，逐个插入到小顶堆中，并更新辅助数组中的父节点信息。插入时可以使用类似于二叉搜索树的插入操作，通过不断地与父节点比较并交换位置来找到合适的插入位置。
步骤二：打印路径。对于每个给定的下标i，从H[i]开始，沿着辅助数组中的父节点指针向上遍历，直到到达根节点。在遍历过程中，按顺序输出路径上的数字，并以空格分隔。注意行末不得有多余空格。
通过上述步骤，我们可以解决给定的问题。具体的代码实现需要根据所选的编程语言和数据结构进行展开。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
