1.题目
https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
2.思路
（1）不可以像以前（如pat1013）用vector数组存储邻接表（否则会报出下面的错误）——因为数组的元素可能是负数！！！
并木有vector<int,vector<int>>，所以使用map<int,vector<int>>adj存储邻接表，所以后面dfs用到的vis访问数组也是map<int,bool>类型而非vector<bool>vis。
Line 78: Char 17: runtime error: load of null pointer of type 'std::_Bit_type' (aka 'unsigned long') (stl_bvector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_bvector.h:87:17
（2）过程：
找到第一个起点（有2个，任意找一个都可以）——根据邻接表的每个点的边表的结点个数为1个即为所求的第一个起点，一开始写的判断条件中size没写==1，而size大于等于1时候也是等于true。
然后dfs遍历一遍二叉树，代码如下，但是这样做的时间复杂度确实高，毕竟这题中这样构造出来的二叉树是个“一条链”，所以还可以优化即不用写dfs。
3.代码
class Solution { public: //vector<bool>vis; unordered_map<int,bool>vis; vector<int>ans; //vector<int>adj[100010];//存储图的邻接表 unordered_map<int,vector<int>>adj; void dfs(int u, unordered_map<int,vector<int> >&vec){ if(vis[u]==false){ ans.push_back(u); vis[u]=true; } for(int i=0;i<adj[u].size();i++){ int v=adj[u][i]; if(vis[v]==false){ dfs(v,adj); } } } vector<int> restoreArray(vector<vector<int>>& adjacentPairs) { //vector<vector<int>>vec=adjacentPairs; vector<vector<int>>vec=adjacentPairs; int group=vec.size(); for(int i=0;i<group;i++){ int a=vec[i][0]; int b=vec[i][1]; adj[a].push_back(b); adj[b].push_back(a); //无向图 } //找第一个点 int first; for(auto it=adj.begin();it!=adj.end();it++){ if(it->second.size()==1){ first=it->first; break; } } dfs(first,adj); return ans; } };
4.不用dfs版本
贴一个大佬sheeeeeeep-t的代码：
class Solution { public: vector<int> restoreArray(vector<vector<int>>& adjacentPairs) { vector<int>ans; set<int>st;//set判某个数是否已经加入了答案数组 unordered_map<int, vector<int>> mp;//哈希表 int n = adjacentPairs.size(); for(int i = 0; i < n; i++){ mp[adjacentPairs[i][0]].push_back(adjacentPairs[i][1]); mp[adjacentPairs[i][1]].push_back(adjacentPairs[i][0]); } int start; //找一个端点 unordered_map<int, vector<int>>::iterator it = mp.begin(); for(; it != mp.end(); it++){ if(it->second.size() == 1){ start = it->first; st.insert(start); ans.push_back(start); break; } } //从端点开始构建整个 答案数组 int temp = start; while(st.size() < n + 1){ for(int i = 0; i < mp[temp].size(); i++){ if(st.find(mp[temp][i]) == st.end()){ temp = mp[temp][i]; ans.push_back(temp); st.insert(temp); break; } } } return ans; } };
