LeetCode 题解工作台
树中可以形成回文的路径数
给你一棵 树 （即，一个连通、无向且无环的图）， 根 节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
class Solution: def countPalindromePaths(self, parent: List[int], s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 树（即，一个连通、无向且无环的图），根 节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。
另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。
找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以 重新排列 形成 回文 的所有节点对 (u, v) ，并返回节点对的数目。
如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 回文 。
示例 1：
输入：parent = [-1,0,0,1,1,2], s = "acaabc" 输出：8 解释：符合题目要求的节点对分别是： - (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。 - (2,3)，路径上字符形成的字符串是 "aca" ，满足回文定义。 - (1,5)，路径上字符形成的字符串是 "cac" ，满足回文定义。 - (3,5)，路径上字符形成的字符串是 "acac" ，可以重排形成回文 "acca" 。
示例 2：
输入：parent = [-1,0,0,0,0], s = "aaaaa" 输出：10 解释：任何满足 u < v 的节点对 (u,v) 都符合题目要求。
提示：
n == parent.length == s.length1 <= n <= 105- 对于所有
i >= 1，0 <= parent[i] <= n - 1均成立 parent[0] == -1parent表示一棵有效的树s仅由小写英文字母组成
解题思路
方法一
class Solution:
def countPalindromePaths(self, parent: List[int], s: str) -> int:
def dfs(i: int, xor: int):
nonlocal ans
for j, v in g[i]:
x = xor ^ v
ans += cnt[x]
for k in range(26):
ans += cnt[x ^ (1 << k)]
cnt[x] += 1
dfs(j, x)
n = len(parent)
g = defaultdict(list)
for i in range(1, n):
p = parent[i]
g[p].append((i, 1 << (ord(s[i]) - ord('a'))))
ans = 0
cnt = Counter({0: 1})
dfs(0, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once and bitmask operations are constant time. Space complexity is O(n) for storing the hashmap of bitmask counts and recursion stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for solutions that efficiently track character counts along tree paths.
- question_mark
Consider using bit manipulation to represent character parity instead of arrays.
- question_mark
Be prepared to explain how DFS and hashmap counting reduce redundant pair checks.
常见陷阱
外企场景- error
Counting all pairs without using bitmask can lead to O(n^2) time and timeouts.
- error
Incorrectly flipping bits for character counts can miscount palindromic paths.
- error
Not handling single-bit differences when checking for palindrome possibilities.
进阶变体
外企场景- arrow_right_alt
Count paths forming palindromes in a tree where each edge has a numeric label instead of a character.
- arrow_right_alt
Return all paths themselves that can form palindromes instead of just counting.
- arrow_right_alt
Allow paths to start or end at any node, not just pairs with u < v.