Prufer 编码的相关概念

Prufer 编码： Prufer 编码是无根树的一种编码方式，Prufer编码和无根树之间可以相互转化。

无根树转化成 Prufer 编码

对于一颗无根树，每次找到一个编号最小的叶节点（度数为 $1$ 的节点），把和编号最小的叶节点相邻的节点输出，然后把编号最小的叶节点删去，继续循环这样的操作直到只剩两个节点，由于最后一个输出的节点是唯一确定的，一定是 $n$，因此不需要输出，到此即得到 Prufer 编码

对于代码实现，可以用 $O(n)$ 的时间复杂度求出一颗无根树的 Prufer 编码。

取一个变量 $j$ 从 $1$ 开始枚举，每次找到第一个叶节点，此时 $j$ 存的就是所有叶节点中编号最小的一个叶节点。把相邻的节点输出，并把编号最小的叶节点删掉。这时最多只会多出一个新的叶节点。

这个新的叶节点会有两种情况，一种是编号大于 $j$，这时最小的叶节点还是 $j$，不用管。另一种是编号小于 $j$，此时 $j$ 就变成新的叶节点。

这样就能在 $O(n)$ 的时间复杂度以内求出无根树的 Prufer 编码。

注意： 在实现过程中，我们将无根树看作一个以 $n$ 为根节点的有根树，由于 $n$ 一定是最后一个，因此结果依然正确且实现更简单。

Prufer 编码转化成无根树

对于一个 Prufer 编码，可以发现每个编号出现几次，就说明它有多少个儿子。虽然 $n$ 没有出现，但是由于 Prufer 编码最后一位固定是 $n$，所以 $n$ 也有一个儿子。然后左往右考虑 Prufer 编码，例如 $3~5~4~5$，第一个是 $3$，最开始叶节点只有 $1$ 和 $2$，输出 $3$ 时是从小到大找叶节点，所以 $3$ 应该是编号最小的叶节点的父亲，此时编号最小的叶节点是 $1$，因此 $1$ 的父亲就是 $3$。此时已经找到 $3$ 的一个儿子，因此 $3$ 的儿子数量 $-1$，然后找 $5$ 的儿子。以此类推，就能找出所有节点的父节点，这样就根据 Prufer 编码转化出一颗无根树。

对于代码实现，同样可以做到 $O(n)$ 的时间复杂度，还是用一个变量 $j$，从前往后枚举当前编号最小的叶节点，然后看 Prufer 编码的每一位 $x$，每次其实就是要把 $j$ 的父节点设成 $x$。然后要把 $j$ 删掉，删掉之后最多只会多一个新的叶节点。

对于这个新的叶节点，一种情况是新的叶节点的编号大于 $j$，那就不用管，继续去枚举 $j$，另一种情况是新的叶节点的编号小于 $j$，由于 $j$ 已经是当前最小值，而新的叶节点的编号更小，说明删掉 $j$ 后，这个新的叶节点就是新的 $j$，可以直接处理新点。

可以发现两种转化方式都是类似的，且都是 $O(n)$ 的时间复杂度，非常简洁迅速。