从相邻元素对还原数组 图解题解

adjacentPairs 只给了相邻关系，要还原成什么

给你一个二维数组 adjacentPairs，长度 n 减 1，每一项 [u, v] 只说明 u 和 v 在原数组 nums 里挨着，但谁左谁右不定、各对也乱序。nums 里的数互不相同、可能为负、绝对值到十万，要把这些散乱的相邻关系拼回 nums。题面 adjacentPairs = [[2,1],[3,4],[3,2]] 还原成 [1,2,3,4]；带负数的例子答案 [-3,1,4,-2]，倒着写也对。

把相邻对排序首尾接起来，为什么接不成链

顺手容易想到把相邻对排序再首尾相接拼成链。可 [u, v] 谁前谁后不定、各对排列也乱，排序无从下手，拼接也不知该接哪端——[2,1] 摆成 …2,1… 还是 …1,2…？排序拼不出唯一顺序。真正稳的信息不是先后，而是「谁和谁相邻」这层关系，得换种结构装它。

相邻对看成边之后，链的两头藏着什么信号

把每一对 [u, v] 看成一条连 u 和 v 的无向边，n 个数就是 n 个点、n 减 1 条边的图。原数组本是一条线：最左的数只有右邻居、最右的只有左邻居，首尾各只连一条边，度，也就是邻居个数，恰好是 1；中间每个数左右各一个邻居，度是 2。两端于是有了精准标记——全图里度为 1 的，只会是链的两端点。

认准度为 1 的端点，带着 prev 把链走通

实现上先用哈希表 g 建邻接表：遍历每对 a、b，往 g[a] 塞 b、g[b] 塞 a，互相登记。建完扫一遍挑出只有一个邻居的键当端点，取较小的作起点 start。再从 start 沿边走：prev 记上一步、cur 记当前点，每到一处先把 cur 填进答案，再选不等于 prev 的那个邻居当下一站 nxt。中间点两个邻居总有一个是 prev，跳过它才不原地折返；走到另一端点时下一站为空，链到头。

顺着 [[2,1],[3,4],[3,2]] 从头建图走一遍

就用题面 adjacentPairs = [[2,1],[3,4],[3,2]]。建图：[2,1] 让 g[2]=[1]、g[1]=[2]；[3,4] 让 g[3]=[4]、g[4]=[3]；[3,2] 再往 g[3] 添 2、g[2] 添 3。最终 g[1]=[2]、g[2]=[1,3]、g[3]=[4,2]、g[4]=[3]。度为 1 的是 1 和 4，取较小的 1 当起点。开走：cur=1 填答案，邻居只有 2，去 2；到 2，邻居 [1,3] 里 1 是 prev 跳过，去 3；到 3，邻居 [4,2] 里 2 是 prev 跳过，去 4；到 4，邻居只剩 prev，下一站为空。答案 [1,2,3,4]，对上题面。

从中间点起步会乱套，负数和 n=2 要不要另写

复杂度很干净：建图、扫端点、沿链各点访问一次，没排序没嵌套循环，时间 O(n)；邻接表条目约为边数两倍，空间 O(n)。几处易走偏：从中间点起步会乱套，它两向都通、一次定不下序，得认准度为 1 的端点再出发；走中间点忘带 prev，会朝来路折回、两点间反复横跳；还有别拿数值直接当下标，值到正负十万会越界。边界上，n 等于 2 时两点都是端点、随便起步都行，含负数照常建图，多解正倒都对。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        for a, b in adjacentPairs:
            g[a].append(b)
            g[b].append(a)
        start = min(x for x, ns in g.items() if len(ns) == 1)
        ans, prev, cur = [], None, start
        while cur is not None:
            ans.append(cur)
            nxt = None
            for v in g[cur]:
                if v != prev:
                    nxt = v
                    break
            prev, cur = cur, nxt
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> g;
        for (auto& e : adjacentPairs) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        int start = INT_MAX;
        for (auto& [x, ns] : g) if (ns.size() == 1) start = min(start, x);
        vector<int> ans;
        int prev = INT_MIN, cur = start;
        while (true) {
            ans.push_back(cur);
            int nxt = INT_MIN;
            for (int v : g[cur]) if (v != prev) { nxt = v; break; }
            if (nxt == INT_MIN) break;
            prev = cur;
            cur = nxt;
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] e : adjacentPairs) {
            g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            g.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);
        }
        int start = Integer.MAX_VALUE;
        for (Map.Entry<Integer, List<Integer>> e : g.entrySet()) if (e.getValue().size() == 1) start = Math.min(start, e.getKey());
        int[] ans = new int[g.size()];
        int prev = Integer.MIN_VALUE, cur = start;
        for (int i = 0; i < ans.length; i++) {
            ans[i] = cur;
            int next = Integer.MIN_VALUE;
            for (int v : g.get(cur)) if (v != prev) { next = v; break; }
            prev = cur;
            cur = next;
        }
        return ans;
    }
}