2025-05-18：判断 DFS 字符串是否是回文串用go语言，给定一棵包

摘要：2025-05-18：判断 DFS 字符串是否是回文串。用go语言，给定一棵包含 n 个节点的树，节点编号从 0 到 n-1，根节点编号为 0。用一个长度为 n 的数组 parent 表示树的结构，其中 parent[i] 代表节点 i 的父节点，且因为 0

2025-05-18：判断 DFS 字符串是否是回文串。用go语言，给定一棵包含 n 个节点的树，节点编号从 0 到 n-1，根节点编号为 0。用一个长度为 n 的数组 parent 表示树的结构，其中 parent[i] 代表节点 i 的父节点，且因为 0 是根节点，所以 parent[0] 必定为 -1。

同时给出一个长度为 n 的字符串 s，s[i] 是节点 i 对应的字符。

定义一个全局字符串 dfsStr 和一个递归函数 dfs(x)：

• 对节点 x 的所有子节点按编号从小到大依次调用 dfs(y)。• 递归调用结束后，将节点 x 对应的字符 s[x] 追加到 dfsStr 末尾。

现在，对每个节点 i（0 ≤ i

• 将 dfsStr 清空。• 调用 dfs(i)。• 判断 dfsStr 是否为回文串，若是，则 answer[i] = true；否则 answer[i] = false。

请编写程序返回数组 answer。

n == parent.length == s.length。

对于所有 i >= 1 ，都有 0

parent[0] == -1。

parent 表示一棵合法的树。

s 只包含小写英文字母。

输入：parent = [-1,0,0,1,1,2], s = "aababa"。

输出：[true,true,false,true,true,true]。

解释：

调用 dfs(0) ，得到字符串 dfsStr = "abaaba" ，是一个回文串。

调用 dfs(1) ，得到字符串dfsStr = "aba" ，是一个回文串。

调用 dfs(2) ，得到字符串dfsStr = "ab" ，不是回文串。

调用 dfs(3) ，得到字符串dfsStr = "a" ，是一个回文串。

调用 dfs(4) ，得到字符串 dfsStr = "b" ，是一个回文串。

调用 dfs(5) ，得到字符串 dfsStr = "a" ，是一个回文串。

题目来自3227。

• 对每个节点 i，我们需要以 i 为根进行后序遍历，得到 dfsStr。• 直接对每个节点单独进行后序遍历的时间复杂度是 O(n^2)，无法处理 n=1e5 的情况。• 优化思路：• 预处理整棵树的后序遍历序列 dfsStr 和时间戳 nodes。• nodes[i] 记录以 i 为根的子树在后序遍历序列中的区间 [begin, end)。• 这样，以 i 为根的 dfsStr 就是 dfsStr 的 [nodes[i].begin, nodes[i].end) 子串。• 我们需要快速判断 dfsStr 的任意子串 [l, r) 是否为回文串。• 使用 Manacher 算法预处理 dfsStr，得到每个位置的最长回文半径。• 将 dfsStr 转换为 t（插入特殊字符 # 和边界字符 ^、$），以便统一处理奇偶长度的回文串。• halfLen[i] 表示 t 中以 i 为中心的最长回文子串的半径。• 通过 halfLen 可以快速判断 dfsStr 的任意子串是否为回文串：• 子串 [l, r) 在 t 中的中心位置是 l + r + 1。• 如果 halfLen[l + r + 1] > r - l，则 [l, r) 是回文串。1. 构建邻接表 g：O(n)。2. 后序遍历和时间戳记录：O(n)（每个节点访问一次）。3. Manacher 算法预处理：O(n)。4. 计算答案：O(n)（每个节点判断一次，isPalindrome 是 O(1)）。• 总时间复杂度：O(n)。1. 邻接表 g：O(n)。2. dfsStr：O(n)。3. nodes 数组：O(n)。4. t 和 halfLen：O(n)。• 总额外空间复杂度：O(n)。package mainimport ( "fmt")func findAnswer(parent int, s string) bool { n := len(parent) g := make(int, n) for i := 1; i = boxR） // 则 halfLen[i] 应先初始化为已知的回文半径 boxR-i，然后再继续暴力匹配 // 否则 halfLen[i] 与 halfLen[i'] 相等 hl = min(halfLen[boxM*2-i], boxR-i) } // 暴力扩展 // 算法的复杂度取决于这部分执行的次数 // 由于扩展之后 boxR 必然会更新（右移），且扩展的的次数就是 boxR 右移的次数 // 因此算法的复杂度 = O(len(t)) = O(n) for t[i-hl] == t[i+hl] { hl++ boxM, boxR = i, i+hl } halfLen[i] = hl } // t 中回文子串的长度为 hl*2-1 // 由于其中 # 的数量总是比字母的数量多 1 // 因此其在 dfsStr 中对应的回文子串的长度为 hl-1 // 这一结论可用在 isPalindrome 中 // 判断左闭右开区间 [l,r) 是否为回文串 0= r-l，即 halfLen[l+r+1] > r-l isPalindrome := func(l, r int)bool { return halfLen[l+r+1] > r-l } ans := make(bool, n) for i, p := range nodes { ans[i] = isPalindrome(p.begin, p.end) } return ans}func main { parent := int{-1, 0, 0, 1, 1, 2} s := "aababa" result := findAnswer(parent, s) fmt.Println(result)}

Rust完整代码如下：

use std::cmp::min;fn find_answer(parent: &[i32], s: &str) -> Vec {let n = parent.len;let mut g = vec![Vec::new; n];for i in 1..n {let p = parent[i] as usize;// 由于 i 递增，g[p] 本身有序，无需排序g[p].push(i);}// dfsStr 存储整棵树的后序遍历字符串let mut dfs_str = vec![0u8; n];// nodes[i] 记录子树 i 的后序遍历区间 (begin, end)let mut nodes = vec![(0, 0); n];let mut time = 0;fn dfs(x: usize,g: &Vec>,s: &[u8],nodes: &mut Vec,dfs_str: &mut Vec,time: &mut usize,) {nodes[x].0 = *time;for &y in &g[x] {dfs(y, g, s, nodes, dfs_str, time);}dfs_str[*time] = s[x];*time += 1;nodes[x].1 = *time;}dfs(0, &g, s.as_bytes, &mut nodes, &mut dfs_str, &mut time);// Manacher 算法处理 dfs_str// 转换字符串 t: ^#a#b#c#...#$let mut t = Vec::with_capacity(n * 2 + 3);t.push(b'^');for &c in &dfs_str {t.push(b'#');t.push(c);}t.push(b'#');t.push(b'$');let m = t.len;// half_len[i]: 以 t[i] 为中心的最长回文半径(包含中心)let mut half_len = vec![0; m - 2];half_len[1] = 1;let mut box_m = 0;let mut box_r = 0;for i in 2..half_len.len {let mut hl = 1;if i r - l;let mut ans = vec![false; n];for i in 0..n {let (begin, end) = nodes[i];ans[i] = is_palindrome(begin, end);}ans}fn main {let parent = vec![-1, 0, 0, 1, 1, 2];let s = "aababa";let result = find_answer(&parent, s);println!("{:?}", result);}

Python完整代码如下：

# -*-coding:utf-8-*-from typing import Listdef find_answer(parent: List[int], s: str) -> List[bool]:n = len(parent)g = [ for _ in range(n)]# 建树，parent[i] 为 i 的父节点，i从1开始for i in range(1, n):p = parent[i]# i 按升序遍历保证子节点列表有序，无需再排序g[p].append(i)dfs_str = [''] * nnodes = [{'begin': 0, 'end': 0} for _ in range(n)]time = 0def dfs(x: int):nonlocal timenodes[x]['begin'] = timefor y in g[x]:dfs(y)dfs_str[time] = s[x]time += 1nodes[x]['end'] = timedfs(0)# Manacher 算法预处理，将 dfs_str 转换为新的串 t# 用特殊字符分割，简化回文判断，避免奇偶问题t = ['^']for c in dfs_str:t.append('#')t.append(c)t.append('#')t.append('$')half_len = [0] * (len(t) - 2)half_len[1] = 1box_m, box_r = 0, 0for i in range(2, len(half_len)):hl = 1if i bool:# 判断 dfs_str[l:r] 是否回文# 回文中心在 t 中位置为 l + r + 1# half_len[i] 表示回文半径，回文长度 = half_len[i] * 2 - 1# 由于分隔符的关系，dfs_str 对应子串长度 = r - l，判断条件为 half_len[l+r+1] > r-lreturn half_len[l + r + 1] > (r - l)ans = [False] * nfor i in range(n):p = nodes[i]ans[i] = is_palindrome(p['begin'], p['end'])return ansif __name__ == "__main__":parent = [-1, 0, 0, 1, 1, 2]s = "aababa"result = find_answer(parent, s)print(result) # 输出示例 [True, True, True, False, False, True]