拼多多Linux Tree

#include <string>
#include <iostream>
#include <map>
#include <functional>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

int n,m;
vector<string> nameMap;//index to name
vector<vector<string>> tree;
map<string, int> nodeIndex;//name to index

void dfs(vector<vector<string>> tree, int root,string mark)
{
	if (root == 0) cout << nameMap[0] << endl;
	if (tree[root].size() > 0)
	{
		for (int i = 0; i < tree[root].size(); ++i)
		{
			if (i < tree[root].size() - 1)
			{
				cout<<mark << "|--" << nameMap[nodeIndex[tree[root][i]]] << endl;
				dfs(tree, nodeIndex[tree[root][i]], mark+"|  ");
			}
			else
			{
				cout<<mark << "`--" << nameMap[nodeIndex[tree[root][i]]] << endl; 
				dfs(tree, nodeIndex[tree[root][i]], mark + "   ");
			}
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	cin >> n;
	tree = vector<vector<string>>(n, vector<string>());
	for (int i = 0; i < n; ++i)
	{
		int parent;
		string tmpStr;
		cin >> tmpStr;
		nameMap.push_back(tmpStr);
		cin >> parent;
		while (nodeIndex.find(tmpStr) != nodeIndex.end())
		{
			tmpStr += "*";
		}
		nodeIndex[tmpStr] = i;
		if (parent > -1)
		{
			tree[parent].push_back(tmpStr);
		}	
	}
	for (int i = 0; i < n; ++i)
	{
		if (tree[i].size() > 0)
		{
			sort(tree[i].begin(), tree[i].end());
		}
	}
	dfs(tree, 0,"");
	return 0;
}

分享一下自己AC的答案，同是没有offer的菜鸟，大家一起加油！#Java工程师##C++工程师#

全部评论

推荐最新楼层

heliar_mk

浙江大学算法工程师

贴一个我的，思路也是用邻接表保存节点的string和他自身是哪一个节点，然后串在每个父节点后面最后dfs。就是前缀的那些符号条件要仔细考虑。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; void DFS(vector<vector<pair<string,int>>> &dir, int root, string mask) { string next_mask; for (int i = 0; i < dir[root].size(); ++i) { pair<string, int> node = dir[root][i]; cout << mask; if (i != dir[root].size() - 1) { cout << "|-- "; } else { cout << "`-- "; } cout << node.first << endl; if (i == dir[root].size() - 1) { next_mask = " " + mask; } else { next_mask = mask + "| "; } DFS(dir, node.second, next_mask); } } bool cmp(pair<string, int> a, pair<string, int> b) { return a.first < b.first; } int main() { int n; cin >> n; vector<vector<pair<string,int>>> dir(n + 1); for (int i = 0; i < n; ++i) { string node_s; int fa_idx; pair<string, int> node; cin >> node_s >> fa_idx; node.first = node_s; node.second = i+1; dir[fa_idx + 1].push_back(node); } for (int i = 0; i < dir.size(); ++i) { sort(dir[i].begin(), dir[i].end(),cmp); } cout << dir[0][0].first << endl; DFS(dir, 1, ""); return 0; }

点赞回复分享

发布于 2017-09-02 19:48

水一样哦哦哦

Conservatorio LUCIO Campiani di MANTOVA C++

分享代码不应该说下思路吗，思路最重要

点赞回复分享

发布于 2017-09-02 17:47

牛妹啊

京东集团_软件开发工程师

大神

点赞回复分享

发布于 2017-09-02 18:20