doocs/leetcode 题解精读：LCP 80「生物进化录」——DFS 贪心构造字典序最小的 01 演化记录串

• 示例工程

本文围绕 doocs/leetcode 仓库中 LCP 80「生物进化录」题解 展开，讲解如何把一棵树形演化结构翻译成01记录串，并通过"DFS 递归构造 + 子树记录串字典序排序"的贪心策略，在n ≤ 10^4的规模下求得字典序最小的复刻串。读完你将掌握这道"树 + 字符串 + 贪心"综合题的完整推导、正确性论证，以及 Python3 / Java / C++ / Go 四种语言实现的关键差异与运行细节。

一、题目背景：把一棵树"说"出来

永恒之森中的生物进化录以树形结构记载所有生物的演化过程。输入数组parents描述了这棵树：parents[i]表示编号i节点的父节点编号，根节点的父节点为-1。炼金术师提出一种方法，用01字符串将演化过程完整复刻下来，规则如下：

初始时指针位于唯一的根节点（演化的起点），随后依次读取01串中的字符执行上述操作。要求返回能够完整复刻演化过程的字符串中，字典序最小的01串。

注意：节点指针最终可以停在任何节点上，不一定要回到根节点。

数据范围（提示）：

• 1 <= parents.length <= 10^4
• -1 <= parents[i] < i（即父节点编号严格小于子节点编号）

一个容易被忽略、但直接影响解法的推论是：由于parents[i] < i，编号0必然是根节点，且建图时父节点总是先于子节点出现，因此只需要从i = 1开始依次把每个节点挂到parents[i]名下即可，无需额外判断合法性。

二、问题转化：一次带回溯标记的先序遍历

把记录规则映射到树的遍历上，可以得到一个关键等价关系：

• 指针从根出发，根节点本身就是起点，不需要任何0来"进入"根；
• 每访问一条父 → 子的边，写一个0（下潜进入子节点）；
• 每从子节点回到父节点，写一个1（上升回溯）；
• 因而任意一个完整记录串，本质上就是一棵树上的先序遍历序列，其中0表示"进入子节点"、1表示"回到父节点"。

生物进化录记录过程的动画演示.gif)

这样一来，问题就变成：在保持"先序访问 + 回溯"约束的前提下，如何安排遍历顺序，使产生的01串字典序最小。全局的自由度只有两个：

1. 同一父节点下各子树（子节点）的访问顺序——这直接影响拼接结果的字典序；
2. 末尾是否省略回溯的1——因为指针不必回到根，末尾的回溯符可以被裁掉。

题目文档的思考块也明确指出了这一点（见 README.md 的thinking段落）："记录规则对应一次先序遍历：进入子节点写0，回溯写1。同一父节点下子树的记录顺序影响整串字典序，且指针最终不必回到根，末尾的回溯可以省略。"

三、示例精讲：从暴力枚举到模式验证

示例 1：parents = [-1, 0, 0, 2]→ 输出"00110"

树结构为：根0有两个子节点1、2，而2又有一个子节点3。共有 2 种完整记录方案：

• 方案 1：0(记录编号 1 的节点) →1(回退至节点 0) →0(记录编号 2 的节点) →0(记录编号 3 的节点)，得到"0100"，指针最终停在节点 3；
• 方案 2：0(记录编号 2 的节点) →0(记录编号 3 的节点) →1(回退至节点 2) →1(回退至节点 0) →0(记录编号 1 的节点)，得到"00110"，指针最终停在节点 1。

逐位比较"00110"与"0100"：首位相同（都是0），第二位0 < 1，因此返回字典序更小的"00110"。

用题解的 DFS 递归验证一遍：叶子节点1、3的记录串均为"01"；节点2的记录串为"0" + "01" + "1" = "0011"；根节点对两个子树串["01", "0011"]排序后得"0011" + "01"，于是dfs(0) = "0" + "0011" + "01" + "1" = "00011011"；去掉首字符得"0011011"，再裁掉末尾连续的1，恰好得到"00110"。

示例 2：parents = [-1, 0, 0, 1, 2, 2]→ 输出"00101100"

逐层构造：3、4、5为叶子（记录串"01"）；节点1的记录串为"0" + "01" + "1" = "0011"；节点2有两个叶子子节点，记录串为"0" + "01" + "01" + "1" = "001011"；根节点对["0011", "001011"]排序（"001011" < "0011"）后拼接，得dfs(0) = "0" + "001011" + "0011" + "1" = "000101100111"。去掉首字符得"00101100111"，再裁掉末尾的1，得到"00101100"，与题目输出一致。

四、核心解法：DFS 递归构造 + 子树串字典序排序

题目文档给出的标准解法是方法一：DFS（Solution.py）：

class Solution: def evolutionaryRecord(self, parents: List[int]) -> str: def dfs(i: int) -> str: t = sorted(dfs(j) for j in g[i]) return "0" + "".join(t) + "1" n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip("1")

整个算法只有三步，但每一步都对应一个不容置疑的结论：

1. 建图：用邻接表g[i]保存节点i的所有子节点。得益于parents[i] < i，从i = 1遍历即可完成建图。
2. 递归构造：dfs(i)返回"从节点i出发、完整记录其整个子树并回到i"的记录串，即"0" + 各子树记录串按字典序排序后拼接 + "1"。这里的0表示"进入i"，末尾的1表示"访问完i的子树后回到父节点"。
3. 两端裁剪：dfs(0)[1:]去掉根节点多余的首字符0（根是起点，不需要"进入"）；.rstrip("1")去掉末尾连续的1（指针不必回到根，末尾回溯符全部省略）。

为什么"排序后拼接"就是字典序最小？

这里需要一个经典的交换论证。设某个节点下有两个子树记录串A、B，且字典序满足A < B。如果保持其他部分的顺序不变，只交换A、B的位置，得到的两种拼接分别为A + B与B + A。要证明"排序后拼接最小"，关键在于合法子树记录串的一个结构性不变量：

• 任意合法子树记录串都以0开头、以1结尾；
• 若把0视为+1、1视为-1，则记录串的前缀和除末位外恒为正（末尾的1才把前缀和归零）。

由这个不变量可以推断：任意两个合法子树记录串互不为对方的真前缀——因为若一个合法串是另一个合法串的前缀，后者在"前缀结束"的位置前缀和必然为0，而合法串内部不允许前缀和归零，矛盾。

而一旦两个字符串互不为真前缀，A < B（字典序）就意味着两者在某个位置首次出现字符差异，且该处A的字符更小，这个差异同样决定了A + B < B + A。于是对每个节点，把子树的记录串按字典序排序再拼接，任何相邻交换都不会使结果变大，局部即达到最优；自底向上归纳，整棵树的记录串达到全局字典序最小。

为什么"去首0、去尾1"合法且必要？

• 去首0：dfs(0)为统一递归格式而在根节点前也加了0，但根本身就是起点，这个"进入根的0"根本不存在，必须删掉；
• 去尾1：末尾的1只做回溯、不记录任何新节点，删去后记录串依然完整复刻了整棵树；且裁剪后的串是原串的前缀，字典序严格更小，所以"能省则省"恰好给出最小串。

顺带一提边界情形：当parents = [-1]（只有根节点）时，dfs(0) = "01"，裁剪后返回空串""，语义上"无演化可记录"，同样自洽。

五、正确性论证框架

把上面的推导整理成可复盘的论证链条：

1. 合法性（双射）：任一01记录串与树上的"进入/回溯"先序访问序列一一对应，dfs(i)构造出的串按定义完整覆盖子树i的全部节点；
2. 无前缀性（结构性不变量）：合法子树记录串内部前缀和恒正、仅末位归零，故任意两个合法子树串互不为真前缀；
3. 局部最优（交换论证）：互不为前缀的两串A < B蕴含A + B < B + A，因此按字典序排序拼接即得该节点下的最小拼接；
4. 全局归纳：假设每个子树的记录串已是最小，则根节点在"最小子串集合"上做字典序排序拼接，所得整串就是全局最小；
5. 裁剪最优：首字符0必须删（不存在的操作），末尾1删尽后串最短且仍合法，前缀关系保证其字典序最小。

四条语言版本的代码实现完全遵循这套论证，只是"去首去尾"的写法不同，见下文。

六、复杂度分析

• 建图：O(n)，一次遍历parents即可；
• 递归：每个节点恰好执行一次dfs，子问题规模为子树大小；
• 排序：每个节点对其子节点记录串排序。整棵树的子树串数量与边数同阶，若按字符串比较成本摊还计算，排序部分可推断为O(n log n)量级；
• 空间：O(n)，包含结果串长度与递归栈深度（递归深度与树高相关，最坏为链状树下的O(n)）。

两个实现层面的注意事项（基于仓库代码可以推断）：

1. 字符串拼接成本：Python3 的"".join(t)、Go 的strings.Join(t, "")是线性拼接；而 Java、C++ 中不可变字符串的反复拼接在链状退化树（每个节点只有一个子节点）下会产生最坏O(n²)的字符拷贝量。好在n ≤ 10^4，该开销仍在可接受范围内；
2. Python 递归深度：当树退化为长链时递归深度可达10^4，超过 Python 默认递归限制（约 1000）。在本地复现时若遇RecursionError，可考虑提高递归上限或改为显式栈的迭代写法。

七、多语言实现对照

题目文档以 tabs 形式给出了四种语言的完整实现（对应仓库中的 Solution.py、Solution.java、Solution.cpp、Solution.go），核心逻辑完全一致，差异只在"去首去尾"的惯用法上。

Python3

class Solution: def evolutionaryRecord(self, parents: List[int]) -> str: def dfs(i: int) -> str: t = sorted(dfs(j) for j in g[i]) return "0" + "".join(t) + "1" n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip("1")

要点：sorted直接按字典序排序生成器结果；rstrip("1")删除末尾全部1。若在本地直接运行，需要from typing import List（在线评测环境通常已内置）。

Java

class Solution { private List<Integer>[] g; public String evolutionaryRecord(int[] parents) { int n = parents.length; g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 1; i < n; ++i) { g[parents[i]].add(i); } return dfs(0).substring(1).replaceAll("1+$", ""); } private String dfs(int i) { List<String> t = new ArrayList<>(); for (int j : g[i]) { t.add(dfs(j)); } Collections.sort(t); return "0" + String.join("", t) + "1"; } }

要点：substring(1)去首；正则"1+$"匹配末尾连续的1并替换为空串，等价于rstrip("1")。

C++

class Solution { public: string evolutionaryRecord(vector<int>& parents) { int n = parents.size(); vector<vector<int>> g(n); for (int i = 1; i < n; ++i) { g[parents[i]].push_back(i); } function<string(int)> dfs = & -> string { vector<string> t; for (int j : g[i]) { t.push_back(dfs(j)); } sort(t.begin(), t.end()); string res = "0"; for (const string& s : t) { res += s; } res += "1"; return res; }; string ans = dfs(0); return ans.substr(1, ans.find_last_not_of('1')); } };

要点：ans.substr(1, ans.find_last_not_of('1'))一步完成"去首 + 裁到最后一个非1字符"两件事。

Go

func evolutionaryRecord(parents []int) string { n := len(parents) g := make([][]int, n) for i := 1; i < n; i++ { g[parents[i]] = append(g[parents[i]], i) } var dfs func(int) string dfs = func(i int) string { var t []string for _, j := range g[i] { t = append(t, dfs(j)) } sort.Strings(t) return "0" + strings.Join(t, "") + "1" } ans := dfs(0)[1:] return strings.TrimRight(ans, "1") }

要点：sort.Strings按字节字典序排序；strings.TrimRight(ans, "1")裁掉末尾所有1，语义与 Python 的rstrip("1")一致。

八、仓库组织与扩展阅读

该题解位于仓库的 LCP 系列目录下，文件组织非常规整：

• 题目与题解文档：lcp/LCP 80. 生物进化录/README.md，包含题目描述、示例、提示、解法思路与多语言代码；
• 题解源码：同目录下的Solution.py、Solution.java、Solution.cpp、Solution.go，与文档中的代码完全一致，可直接复制到本地或在线评测环境运行；
• 配图资源：同目录images/下存放了示例 1 的树形结构图与记录过程动画，分别用于解释输入与规则；
• 系列索引：lcp/README.md 汇总了全部 LCP 题目，可用Control/Command + F按题号快速检索。

仓库中每个题解目录都遵循"README 文档 + 多语言 Solution 源码"的同一模式，便于对照学习不同语言对同一算法的惯用写法。若想在本地复现本题，只需将对应语言的Solution代码粘贴到支持的环境（如在线评测平台或本地解释器）中，传入题目给定的parents数组即可，无需额外依赖。

九、小结与延伸思考

LCP 80「生物进化录」的解法可以提炼为一套可迁移的解题框架：

1. 把结构翻译成事件序列：树上的"进入（0）/ 回溯（1）"天然对应一次带括号语义的先序遍历，先把规则转成遍历问题；
2. 识别自由度：本题的自由度只有"同一父节点下子树的访问顺序"与"末尾是否省略回溯"，这是贪心可以介入的入口；
3. 交换论证 + 结构性不变量：通过"合法子树串互不为前缀"这一前缀和不变量，证明按字典序排序拼接即最优；
4. 两端裁剪：根的首0与末尾可省略的1必须裁掉，裁剪后的串最短且字典序更小。

这种"用字符串复刻树/图结构并求字典序最小"的思路，与树的序列化（如括号表示法、欧拉序）一脉相承——把结构编码成序列、再对序列做最小化，是树相关字符串问题中非常值得复用的思考方式。遇到同类题目时，不妨先问自己三个问题：事件序列如何定义？自由度在哪里？裁剪规则是否合法且必要？

• 示例工程