千问 LeetCode 2791. 树中可以形成回文的路径数 Java实现
这是一道经典的树上路径计数问题，结合了状态压缩和异或（XOR）的技巧。
核心思路
1. 回文判断条件：一个字符串的字符重新排列后能形成回文，当且仅当字符串中最多只有一个字符出现了奇数次，其余字符均出现偶数次。
2. 状态压缩与异或：由于字符串只包含小写字母（26个），我们可以用一个 26 位的二进制数（int 类型）来表示当前路径上各字符出现次数的奇偶性。某一位为 1 表示该字符出现了奇数次，为 0 表示出现了偶数次。在树上遍历时，向下走一条边相当于对该边字符对应的二进制位进行异或操作。
3. 路径转化：树上任意两点 u 到 v 的路径，可以看作是从 u 到根节点，再从根节点到 v 的路径。其中，从 u 和 v 的最近公共祖先（LCA）到根节点的这段路径被重复走了两次（一去一回），字符出现次数必然为偶数（异或后为0），不影响回文判断。因此，我们只需要记录每个节点到根节点的路径状态。
4. 计数逻辑：使用 DFS 遍历树，并用一个哈希表（HashMap）记录遍历过程中，各种路径状态出现的次数。对于当前节点，如果之前存在一个节点到根节点的状态与当前状态完全相同（异或结果为0，所有字符均为偶数次）或仅相差一位（异或结果只有一个1，仅一个字符为奇数次），那么这两个节点之间的路径就能形成回文。
Java 代码实现
import java.util.*;
class Solution {
public long countPalindromePaths(List<Integer> parent, String s) {
int n = parent.size();
// 1. 构建邻接表（树结构）
List<Integer>[] children = new ArrayList[n];
Arrays.setAll(children, e -> new ArrayList<>());
for (int i = 1; i < n; i++) {
int p = parent.get(i);
children[p].add(i);
}
// 2. 哈希表记录从根节点到当前路径的状态（异或值）出现的次数
// 初始放入 0:1，代表根节点之上的空路径状态
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1);
return dfs(0, 0, children, s.toCharArray(), count);
}
private long dfs(int node, int status, List<Integer>[] children, char[] chars, Map<Integer, Integer> count) {
long res = 0;
for (int child : children[node]) {
// 计算从根节点到子节点 child 的路径状态
// 异或上当前边上的字符对应的位
int childStatus = status ^ (1 << (chars[child] - 'a'));
// 情况1：之前有相同状态的路径（所有字符出现偶数次，异或后为0）
res += count.getOrDefault(childStatus, 0);
// 情况2：之前有仅相差一个字符奇偶性的路径（仅一个字符出现奇数次）
for (int i = 0; i < 26; i++) {
res += count.getOrDefault(childStatus ^ (1 << i), 0);
}
// 将当前子节点的状态加入哈希表，供后续节点匹配
count.put(childStatus, count.getOrDefault(childStatus, 0) + 1);
// 继续向下 DFS
res += dfs(child, childStatus, children, chars, count);
}
return res;
}
}
复杂度分析
* 时间复杂度：O(n * A)，其中 n 是节点数量，A 是字符集大小（本题为26）。每个节点只会被遍历一次，每次遍历需要枚举 26 个字母来寻找只差一位的状态。
* 空间复杂度：O(n)，主要用于存储树的邻接表以及哈希表。在最坏情况下（如链状树），哈希表可能存储 O(n) 个不同的状态。