树状结构查询 - 华为OD统一考试

OD统一考试

分值： 200分

题解： Java / Python / C++

alt

题目描述

通常使用多行的节点、父节点表示一棵树，比如：

西安陕西

陕西中国

江西中国

中国亚洲

泰国亚洲

输入一个节点之后，请打印出来树中他的所有下层节点。

输入描述

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

接着是查询节点

输出描述

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

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

示例1

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

输出：
d
e
f

题解

这道题是一个树的遍历问题，首先构建树的结构，然后深度优先遍历 (DFS) 树的某一节点，收集其所有下层节点并按字典序排序输出。

Java、Python、C++ 代码中，都定义了一个 Node 类表示树的节点，包含节点名称和子节点列表。然后通过输入的边信息构建了这个树的结构，最后进行 DFS 遍历。

下面是一些关键点的总结：

树的表示： 使用 Node 类表示树的节点，通过 addChild 方法构建父子关系，通过 dfs 方法进行深度优先遍历。
DFS 遍历： 递归地遍历树的节点，将每个子节点的名称收集起来，最后按字典序排序。
输入处理： 使用 Scanner（Java）、input()（Python）、cin（C++）等方式读取输入。
数据结构选择： 在 Java 和 Python 中，使用了 ArrayList 和列表（list）作为存储子节点的数据结构；在 C++ 中，使用了 vector。
节点查找： 通过构建的树结构，可以通过输入的关键节点找到相应的节点，然后进行 DFS 遍历。

总体而言，这个问题是一个典型的树的深度优先遍历问题，通过递归的方式遍历树的节点，按字典序排序输出结果。

Java

import java.util.*;
/**
 * @author code5bug
 */
class Node {
    String name;
    List<Node> children;

    public Node(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

    void addChild(Node child) {
        children.add(child);
    }
}

public class Main {
    public static void dfs(Node node, List<String> collect) {
        for (Node child : node.children) {
            collect.add(child.name);
            dfs(child, collect);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Map<String, Node> nodeMap = new HashMap<>();

        // 构建父子关系
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < n; ++i) {
            String[] input = scanner.nextLine().split(" ");
            String child = input[0];
            String parent = input[1];

            nodeMap.computeIfAbsent(child, Node::new);
            nodeMap.computeIfAbsent(parent, Node::new);
            nodeMap.get(parent).addChild(nodeMap.get(child));
        }

        List<String> result = new ArrayList<>();
        String keyword = scanner.nextLine();
        dfs(nodeMap.get(keyword), result);

        result.stream()
                .sorted(Comparator.naturalOrder())
                .forEach(System.out::println);

    }
}

Python

class Node:
    def __init__(self, name):
        self.name = name
        self.children = []

    def addChild(self, child):
        self.children.append(child)


# 缓存所有的节点
node_map = {}
# 构建父子关系
for _ in range(int(input())):
    child, parent = input().split()
    node_map.setdefault(child, Node(child))
    node_map.setdefault(parent, Node(parent))
    node_map[parent].addChild(node_map[child])


def dfs(node, collect):
    """收集所有的子节点的名称到 collect 中"""
    for child in node.children:
        collect.append(child.name)
        dfs(child, collect)


result = []
dfs(node_map[input()], result)
result.sort()
print(*result, sep="\n")

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class Node {
public:
    string name;
    vector<Node> children;

    Node(){}

    Node(string name) : name(name) {}

    void addChild(const Node& child) {
        children.push_back(child);
    }
};

void dfs(const Node& node, vector<string>& collect) {
    for (const Node& child : node.children) {
        collect.push_back(child.name);
        dfs(child, collect);
    }
}

int main() {
    unordered_map<string, Node> node_map;

    int n;
    cin >> n;

    // 构建父子关系
    for (int i = 0; i < n; ++i) {
        string child, parent;
        cin >> child >> parent;

        node_map.emplace(child, Node(child));
        node_map.emplace(parent, Node(parent));

        node_map[parent].addChild(node_map[child]);
    }

    string keyword;
    cin >> keyword;

    vector<string> result;
    dfs(node_map[keyword], result);
    sort(result.begin(), result.end());

    for (const string& name : result) {
        cout << name << endl;
    }

    return 0;
}