#P3251. 树状结构查询(200分)
-
1000ms
Tried: 64
Accepted: 28
Difficulty: 3
所属公司 :
华为od
树状结构查询(200分)
题目描述
在这道题中,我们需要处理一棵树的节点关系,并根据输入的节点查询其所有下层节点(子节点)。输入包括节点及其父节点的关系,最后输入一个查询节点。我们需要输出该节点的所有下层节点,并按照字典序排序。
思路
-
数据结构选择:我们可以使用一个字典(哈希表)来存储树的结构。字典的键是父节点,值是一个列表,包含所有该父节点的子节点。
-
输入处理:首先读取输入的数据,构建树的字典结构。
-
查询处理:对于输入的查询节点,检查字典中是否存在该节点,如果存在,则获取其子节点列表,并进行排序。
-
输出结果:最后,按照字典序输出所有的下层节点。
代码分析
-
库的使用:使用了
<iostream>进行输入输出,<vector>和<map>存储树的结构,<algorithm>进行排序。 -
数据结构:
map<string, vector<string>> tree:使用map存储父节点到子节点的映射关系,vector用于存储一个父节点的所有子节点。
-
读取输入:通过循环读取节点关系,并填充到
tree中。 -
查询节点:
- 使用
tree.find(query)检查查询节点是否存在。 - 如果存在,则取出子节点并进行字典序排序。
- 使用
-
输出结果:按照要求逐行输出结果。
cpp
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
// 深度优先搜索获取所有下层节点
void dfs(const string& node, const map<string, vector<string>>& tree, set<string>& result) {
if (tree.find(node) != tree.end()) {
for (const string& child : tree.at(node)) {
result.insert(child); // 插入子节点到结果集中
dfs(child, tree, result); // 递归访问子节点
}
}
}
int main() {
int n; // 存储输入行数
cin >> n;
cin.ignore(); // 忽略换行符
map<string, vector<string>> tree; // 存储树的结构
// 读取节点与父节点的关系
for (int i = 0; i < n; ++i) {
string child, parent;
cin >> child >> parent;
tree[parent].push_back(child); // 将子节点加入父节点的列表中
}
string query; // 查询节点
cin >> query;
set<string> childrenSet; // 用于存储所有下层节点
dfs(query, tree, childrenSet); // 执行深度优先搜索
// 将结果转为向量并排序
vector<string> children(childrenSet.begin(), childrenSet.end());
sort(children.begin(), children.end());
// 输出下层节点
for (const string& child : children) {
cout << child << endl; // 输出下层节点
}
return 0;
}
python
def dfs(node, tree, result):
if node in tree:
for child in tree[node]:
result.add(child) # 插入子节点到结果集中
dfs(child, tree, result) # 递归访问子节点
def main():
n = int(input()) # 存储输入行数
tree = {} # 存储树的结构
# 读取节点与父节点的关系
for _ in range(n):
child, parent = input().split()
if parent not in tree:
tree[parent] = []
tree[parent].append(child) # 将子节点加入父节点的列表中
query = input() # 查询节点
children_set = set() # 用于存储所有下层节点
dfs(query, tree, children_set) # 执行深度优先搜索
# 将结果转为列表并排序
children = sorted(children_set)
# 输出下层节点
for child in children:
print(child) # 输出下层节点
if __name__ == "__main__":
main()
java
import java.util.*;
public class Main {
// 深度优先搜索获取所有下层节点
public static void dfs(String node, Map<String, List<String>> tree, Set<String> result) {
if (tree.containsKey(node)) {
for (String child : tree.get(node)) {
result.add(child); // 插入子节点到结果集中
dfs(child, tree, result); // 递归访问子节点
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 存储输入行数
scanner.nextLine(); // 忽略换行符
Map<String, List<String>> tree = new HashMap<>(); // 存储树的结构
// 读取节点与父节点的关系
for (int i = 0; i < n; i++) {
String line = scanner.nextLine();
String[] parts = line.split(" ");
String child = parts[0];
String parent = parts[1];
// 将子节点加入父节点的列表中
tree.putIfAbsent(parent, new ArrayList<>());
tree.get(parent).add(child);
}
String query = scanner.nextLine(); // 查询节点
Set<String> childrenSet = new HashSet<>(); // 用于存储所有下层节点
dfs(query, tree, childrenSet); // 执行深度优先搜索
// 将结果转为列表并排序
List<String> children = new ArrayList<>(childrenSet);
Collections.sort(children);
// 输出下层节点
for (String child : children) {
System.out.println(child); // 输出下层节点
}
scanner.close(); // 关闭扫描器
}
}
题目内容
通常使用多行的节点、父节点表示一棵树,比如
西安 陕西
陕西 中国
江西 中国
中国 亚洲
泰国 亚洲
输入一个节点之后,请打印出来树中他的所有下层节点
输入描述
第一行输入行数,下面是多行数据,每行以空格区分节点和父节点
接着是查询节点
输出描述
输出查询节点的所有下层节点。以字典序排序
备注
树中的节点是唯一的,不会出现两个节点,是同一个名字
样例1
输入
5
b a
c a
d c
e c
f d
c
输出
d
e
f