千问 LeetCode 2791. 树中可以形成回文的路径数 C语言实现
在 C 语言中实现这道题，最大的挑战在于 C 标准库没有内置的哈希表（如 Java 的 HashMap 或 Python 的 dict）。因此，我们需要手动实现一个简单的哈希表来记录路径状态的出现次数。
以下是完整的 C 语言实现代码，包含详细注释：
C 语言代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈希表节点
typedef struct HashNode {
int key; // 状态压缩后的异或值
int val; // 该状态出现的次数
struct HashNode* next;
} HashNode;
// 定义哈希表
typedef struct {
HashNode** buckets;
int capacity;
} HashMap;
// 初始化哈希表
HashMap* createHashMap(int capacity) {
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
map->capacity = capacity;
map->buckets = (HashNode**)calloc(capacity, sizeof(HashNode*));
return map;
}
// 哈希函数
int hash(int key, int capacity) {
return (key & 0x7FFFFFFF) % capacity;
}
// 获取值，如果不存在返回 0
int get(HashMap* map, int key) {
int index = hash(key, map->capacity);
HashNode* node = map->buckets[index];
while (node) {
if (node->key == key) return node->val;
node = node->next;
}
return 0;
}
// 增加计数
void put(HashMap* map, int key) {
int index = hash(key, map->capacity);
HashNode* node = map->buckets[index];
while (node) {
if (node->key == key) {
node->val++;
return;
}
node = node->next;
}
// 如果不存在，插入新节点
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->val = 1;
newNode->next = map->buckets[index];
map->buckets[index] = newNode;
}
// 释放哈希表内存
void freeHashMap(HashMap* map) {
for (int i = 0; i < map->capacity; i++) {
HashNode* node = map->buckets[i];
while (node) {
HashNode* temp = node;
node = node->next;
free(temp);
}
}
free(map->buckets);
free(map);
}
// DFS 遍历树
void dfs(int node, int status, int* graph[], int* graphSizes, char* s, HashMap* count, long long* result) {
for (int i = 0; i < graphSizes[node]; i++) {
int child = graph[node][i];
// 计算从根节点到子节点 child 的路径状态（异或当前边的字符）
int childStatus = status ^ (1 << (s[child] - 'a'));
// 情况1：之前有相同状态的路径（所有字符出现偶数次）
*result += get(count, childStatus);
// 情况2：之前有仅相差一个字符奇偶性的路径（仅一个字符出现奇数次）
for (int j = 0; j < 26; j++) {
*result += get(count, childStatus ^ (1 << j));
}
// 将当前子节点的状态加入哈希表
put(count, childStatus);
// 继续向下 DFS
dfs(child, childStatus, graph, graphSizes, s, count, result);
}
}
long long countPalindromePaths(int* parent, int parentSize, char* s) {
// 1. 构建邻接表（树结构）
int** graph = (int**)malloc(parentSize * sizeof(int*));
int* graphSizes = (int*)calloc(parentSize, sizeof(int));
// 先统计每个节点的子节点数量
for (int i = 1; i < parentSize; i++) {
graphSizes[parent[i]]++;
}
// 分配内存
for (int i = 0; i < parentSize; i++) {
graph[i] = (int*)malloc(graphSizes[i] * sizeof(int));
graphSizes[i] = 0; // 重置为 0，用于后续填充
}
// 填充邻接表
for (int i = 1; i < parentSize; i++) {
int p = parent[i];
graph[p][graphSizes[p]++] = i;
}
// 2. 初始化哈希表，初始放入 0:1（代表空路径状态）
HashMap* count = createHashMap(200003); // 使用一个较大的质数作为容量
put(count, 0);
long long result = 0;
// 3. 从根节点 0 开始 DFS
dfs(0, 0, graph, graphSizes, s, count, &result);
// 4. 释放内存
freeHashMap(count);
for (int i = 0; i < parentSize; i++) {
free(graph[i]);
}
free(graph);
free(graphSizes);
return result;
}
核心逻辑与注意事项
1. 手动实现哈希表：由于 C 语言没有内置的哈希表，这里使用拉链法（数组 + 链表）实现了一个简易的 HashMap，提供了 createHashMap、get、put 和 freeHashMap 四个基础操作。
2. 构建邻接表：题目给出的是 parent 数组，我们需要先遍历一次将其转化为子节点的邻接表 graph，方便后续进行 DFS 向下遍历。
3. 状态压缩与异或：利用 int 类型的 26 个二进制位来记录字符出现次数的奇偶性。1 << (s[child] - 'a') 用来定位当前字符对应的二进制位，通过异或操作来更新状态。
4. 计数逻辑：
* 如果当前路径状态 childStatus 在哈希表中已经存在，说明存在一条路径与当前路径异或后为 0（所有字符均为偶数次），可以组成回文。
* 枚举 26 个字母，如果 childStatus ^ (1 << i) 在哈希表中存在，说明存在一条路径与当前路径异或后只有一个字符是奇数次，也可以组成回文。
5. 内存管理：C 语言需要手动 malloc 和 free。在函数结束前，务必释放邻接表、graphSizes 数组以及哈希表占用的堆内存，防止内存泄漏。