华为OD机试 树状结构查询

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

输入描述

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

接着是查询节点

输出描述

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

备注

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

用例

输入

5

b a

c a

d c

e c

f d

c

输出

d

e

f

#include <bits/stdc++.h>
using namespace std;

int main() {
	map<char, vector<char>>p;//map的first存储父节点 second以vector形式存储子节点
	vector<char>result;//存储最终结果的数组
	int n;
	char a, b;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		p[b].push_back(a);
	}
	char tgt;
	cin >> tgt;
	queue<char>q;//bfs用队列
	q.push(tgt);
	while (!q.empty()) {
		char c = q.front();//队列非空就弹出队头元素
		q.pop();
		for (int i = 0; i < p[c].size(); i++) {//将队头元素的子节点压入队列 同时压入result数组中
			q.push(p[c][i]);
			result.push_back(p[c][i]);
		}
	}	
	sort(result.begin(), result.end());//对result数组内容排序
	for (int i = 0; i < result.size(); i++) {
		cout<<result[i]<<endl;
	}
}

#include <bits/stdc++.h>
using namespace std;

void dfs(map<char, vector<char>>p, char tgt, vector<char>&result) {//递归函数， tgt是目标点也就是正在访问的节点
	vector<char>tmp;//存储当前节点的子节点
	if (p.find(tgt) == p.end())//返回条件：map【target】没有对应项，说明该元素无孩子节点
		return;
	else if (p.find(tgt) != p.end()) {//能找到子节点
		for (int i = 0; i < p[tgt].size(); i++) {
			result.push_back(p[tgt][i]);//将该点的所有子节点依次存入result数组
			tmp.push_back(p[tgt][i]);//将该点的所有子节点依次存入tmp数组 
		}
		for (int j = 0; j < tmp.size(); j++)//继续递归，依次递归所有子节点
			dfs(p, tmp[j], result);
	}
}
int main() {
	map<char, vector<char>>p;
	vector<char>result;
	int n;
	char a, b;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		p[b].push_back(a);
	}
	char tgt;
	cin >> tgt;
	dfs(p,tgt,result)//这里将while循环换成了递归
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout<<result[i]<<endl;
	}
}