class Solution {
public:
string evolutionaryRecord(vector<int>& parents) {
}
};
LCP 80. 生物进化录
在永恒之森中,存在着一本生物进化录,以 一个树形结构 记载了所有生物的演化过程。经过观察并整理了各节点间的关系,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"
{:width=120px}{:width=320px}
示例 2:
输入:
parents = [-1,0,0,1,2,2]
输出:
"00101100"
提示:
1 <= parents.length <= 10^4
-1 <= parents[i] < i
(即父节点编号小于子节点)原站题解
golang 解法, 执行用时: 268 ms, 内存消耗: 10 MB, 提交时间: 2023-05-08 10:16:51
func evolutionaryRecord(parents []int) string { n := len(parents) g := make([][]int, n) for w := 1; w < n; w++ { p := parents[w] g[p] = append(g[p], w) // 建树 } var dfs func(int) string dfs = func(v int) string { a := make([]string, len(g[v])) for i, w := range g[v] { a[i] = dfs(w) } sort.Strings(a) return "0" + strings.Join(a, "") + "1" } return strings.TrimRight(dfs(0)[1:], "1") // 去掉根节点以及返回根节点的路径 }
python3 解法, 执行用时: 300 ms, 内存消耗: 33.2 MB, 提交时间: 2023-05-08 10:16:37
class Solution: def evolutionaryRecord(self, parents: List[int]) -> str: n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) # 建树 def dfs(x: int) -> str: a = sorted(dfs(y) for y in g[x]) return "0" + ''.join(a) + "1" return dfs(0)[1:].rstrip('1') # 去掉根节点以及返回根节点的路径