生物进化录

标签:

难度: Hard

在永恒之森中，存在着一本生物进化录，以 **一个树形结构** 记载了所有生物的演化过程。经过观察并整理了各节点间的关系，`parents[i]` 表示编号 `i` 节点的父节点编号(根节点的父节点为 `-1`)。 为了探索和记录其中的演化规律，队伍中的炼金术师提出了一种方法，可以以字符串的形式将其复刻下来，规则如下： - 初始只有一个根节点，表示演化的起点，依次记录 `01` 字符串中的字符， - 如果记录 `0`，则在当前节点下添加一个子节点，并将指针指向新添加的子节点； - 如果记录 `1`，则将指针回退到当前节点的父节点处。 现在需要应用上述的记录方法，复刻下它的演化过程。请返回能够复刻演化过程的字符串中， **字典序最小** 的 `01` 字符串。 **注意：** - 节点指针最终可以停在任何节点上，不一定要回到根节点。 **示例 1：** > 输入：`parents = [-1,0,0,2]` > > 输出：`"00110"` > >解释：树结构如下图所示，共存在 2 种记录方案： >第 1 种方案为：0(记录编号 1 的节点) -> 1(回退至节点 0) -> 0(记录编号 2 的节点) -> 0((记录编号 3 的节点)) >第 2 种方案为：0(记录编号 2 的节点) -> 0(记录编号 3 的节点) -> 1(回退至节点 2) -> 1(回退至节点 0) -> 0(记录编号 1 的节点) >返回字典序更小的 `"00110"` ![image.png](https://pic.leetcode.cn/1682319485-cRVudI-image.png){:width=120px}![进化 (3).gif](https://pic.leetcode.cn/1682412701-waHdnm-%E8%BF%9B%E5%8C%96%20\(3\).gif){:width=320px} **示例 2：** > 输入：`parents = [-1,0,0,1,2,2]` > > 输出：`"00101100"` **提示：** - `1 <= parents.length <= 10^4` - `-1 <= parents[i] < i` (即父节点编号小于子节点)

Submission

运行时间: 204 ms

内存: 25.1 MB

from typing import List
from collections import defaultdict, deque


class Solution:
    def evolutionaryRecord(self, parents: List[int]) -> str:
        """
        :param parents:
        :return:
        """
        m1 = defaultdict(list)
        for k, v in enumerate(parents):
            m1[v].append(k)

        def build_str(start):
            clist = m1.get(start, [])
            if len(clist) == 0:
                return ""
            anslist = ["0"+build_str(i)+'1' for i in clist]
            anslist.sort()
            return "".join(anslist)

        ret = build_str(m1.get(-1)[0])
        return ret[:ret.rfind('0')+1]

Explain

题解采用深度优先搜索（DFS）的方法来构建演化序列。首先，使用一个字典 `m1` 来存储每个节点及其对应的子节点列表。这是通过遍历 `parents` 数组得到的，其中每个元素的索引表示节点，值表示其父节点。对于根节点（其父节点为 `-1`），启动DFS过程。在DFS函数 `build_str` 中，对于每个节点，首先获取其所有子节点，并对每个子节点递归调用 `build_str`。每次递归返回的字符串表示该子节点及其所有后代的演化过程。对这些字符串进行排序，确保按字典序最小方式合并。每个子节点序列前后分别添加 '0' 和 '1'，以模拟在该节点下添加新子节点和回退到父节点的操作。最后，返回构建的字符串，保留到最后一个 '0' 以确保不会多余地回退到根节点之外。

时间复杂度: O(n log n)

空间复杂度: O(n)

from typing import List
from collections import defaultdict, deque


class Solution:
    def evolutionaryRecord(self, parents: List[int]) -> str:
        # 创建一个字典来存储每个节点的子节点列表
        m1 = defaultdict(list)
        for k, v in enumerate(parents):
            m1[v].append(k)

        # DFS函数，用于构建符合条件的字符串
        def build_str(start):
            # 获取当前节点的所有子节点
            clist = m1.get(start, [])
            # 如果没有子节点，返回空字符串
            if len(clist) == 0:
                return ""
            # 递归构建所有子节点的演化序列，并排序
            anslist = ["0"+build_str(i)+"1" for i in clist]
            anslist.sort()
            return "".join(anslist)

        # 从根节点开始构建序列
        ret = build_str(m1.get(-1)[0])
        # 返回序列，确保不包含多余的回退操作
        return ret[:ret.rfind('0')+1]

Explore

在构建字符串时，使用'0'和'1'来标记每个子节点的开始和结束，这种表示方法类似于括号表达式中的左括号和右括号，用于明确定义每个子节点及其后代的边界。这样的设计有助于在递归过程中清晰地识别和构造每一个节点的演化序列，并在合并或者回退到父节点时保持结构的完整性。'0'的添加意味着进入一个新的子节点的演化序列，而'1'的添加则标志着该序列的结束并回退到当前节点，确保构建的字符串可以正确反映整个演化树的结构。

在DFS函数中对子节点序列进行排序是为了确保无论输入节点的顺序如何，最终构建的演化序列都是按照字典序最小排列的。这种排序确保当有多个子节点时，它们的演化序列以最优的顺序合并，从而达到全局的字典序最小。这是关键的，因为不同的合并顺序会产生不同的结果，而排序保证了无论节点如何展开，其结果始终是最小可能的字典序。因此，排序对于达到最终的字典序最小结果具有决定性影响。

题解中使用ret.rfind('0')+1是为了找到演化序列中最后一个'0'的位置，并据此确定返回字符串的长度，确保不包含对根节点之外的多余回退操作。在DFS构建过程中，每个节点的结束都会添加一个'1'，表示回退到父节点。因此，整个演化序列的末尾通常会有多余的'1'，这些'1'如果没有对应的'0'进行平衡，就意味着这些回退操作是多余的，可能会回退到根节点之外。通过裁剪到最后一个'0'，我们确保所有的回退操作都是有效且必要的，符合演化树的结构逻辑，避免了生成无效或错误的演化路径。