存在一個由 n 個不同元素組成的整數數組 nums ，但你已經記不清具體內容。好在你還記得 nums 中的每一對相鄰元素。
給你一個二維整數數組 adjacentPairs ，大小為 n - 1 ，其中每個 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相鄰。
題目數據保證所有由元素 nums[i] 和 nums[i+1] 組成的相鄰元素對都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。這些相鄰元素對可以 按任意順序 出現。
返回 原始數組 nums 。如果存在多種解答，返回 其中任意一個 即可。
- 示例 1：
輸入：adjacentPairs = [[2,1],[3,4],[3,2]]
輸出：[1,2,3,4]
解釋：數組的所有相鄰元素對都在 adjacentPairs 中。
特別要注意的是，adjacentPairs[i] 只表示兩個元素相鄰，并不保證其 左-右 順序。
- 示例 2：
輸入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
輸出：[-2,4,1,-3]
解釋：數組中可能存在負數。
另一種解答是 [-3,1,4,-2] ，也會被視作正確答案。
- 示例 3：
輸入：adjacentPairs = [[100000,-100000]]
輸出：[100000,-100000]
解題思路
- 使用圖表示鄰接關系，數組的每個元素當成是一個節點，除了首尾元素以外，每個節點在數組中應該前后相鄰兩個節點，根據記錄數組中相鄰元素的adjacentPairs，構建出圖
- 遍歷每個節點的鄰接點的個數，個數為1的數組的首尾元素
- 對圖進行深度優先搜索，以數組的首尾元素為起點，遍歷圖的路徑就是數組的順序
代碼
class Solution {public int[] restoreArray(int[][] adjacentPairs) {int n=adjacentPairs.length+1;Map<Integer,List<Integer>> map=new HashMap<>();for (int[] pair : adjacentPairs) {map.putIfAbsent(pair[0],new ArrayList<>());map.get(pair[0]).add(pair[1]);map.putIfAbsent(pair[1],new ArrayList<>());map.get(pair[1]).add(pair[0]);}int s=-1;for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {if(entry.getValue().size()==1){s=entry.getKey();break;}}ArrayList<Integer> list = new ArrayList<>();dfsRestoreArray(n,list,-1,s,map);int[] res = new int[n];for (int i=0;i<n;i++)res[i]=list.get(i);return res;}public void dfsRestoreArray(int n,List<Integer> list,int pre,int cur, Map<Integer,List<Integer>> map) {list.add(cur);for (Integer next : map.get(cur)) {if (next==pre)continue;dfsRestoreArray(n,list,cur,next,map);}}
}
)