树状结构查询

题目描述

通常使用多行的节点、父节点表示一棵树，比如 西安 陕西 陕西 中国 江西 中国 中国 亚洲 泰国 亚洲 输入一个节点之后，请打印出来树中他的所有下层节点

输入描述

第一行输入行数，下面是多行数据，每行以空格区分节点和父节点，接着是查询节点。

输出描述

输出查询节点的所有下层节点。以字典序排序。

补充说明

树中的节点是唯一的，不会出现两个节点，是同一个名字

示例1

输入：
5
b a
c a
d c
e c
f d
c

输出：
d
e
f

题解

题目类型

这道题属于 树的遍历 类问题，可以使用 深度优先搜索（DFS） 来遍历树的所有节点。我们需要递归遍历树的下层节点，并输出结果。

解题思路

1. 构建树：我们首先通过输入的数据构建树的父子关系，可以使用一个字典（或哈希表）来表示树结构，字典的键是父节点，值是该父节点的子节点列表。
2. 深度优先搜索（DFS）：通过递归的方式，遍历给定节点的所有下层节点。每次递归时，访问该节点并将其加入到结果列表中。
3. 字典序排序：DFS遍历结束后，收集的节点按字典序排序，最终输出排序后的节点。

C++

#include <bits/stdc++.h>

using namespace std;

// 深度优先搜索 (DFS)
void dfs(unordered_map<string, vector<string>> &tree, string &node, vector<string> &collect) {
    collect.push_back(node);
    for (string &son: tree[node]) {
        dfs(tree, son, collect);
    }
}

int main() {
    int n;
    cin >> n;  // 输入节点数

    unordered_map<string, vector<string>> tree;  // 存储父子关系的树
    for (int i = 0; i < n; ++i) {
        string son, parent;
        cin >> son >> parent;  // 输入每对父子关系
        tree[parent].push_back(son);  // 将 son 添加到 parent 的子节点列表中
    }

    string key;
    cin >> key;  // 输入要查询的节点

    // 存储结果的集合
    vector<string> result;
    for (string &son: tree[key]) {
        dfs(tree, son, result);  // 对每个子节点进行 DFS
    }

    // 将结果进行字典序排序
    sort(result.begin(), result.end());

    // 输出结果
    for (const string &node: result) {
        cout << node << endl;
    }

    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏