blob: 183e19f99b4ceca153f0feb35ce4f78a26c01275 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
// 1457. Pseudo-Palindromic Paths in a Binary Tree
#include "leetcode.h"
/*
* given a binary tree where node values are digits from 1 to 9. a path in the
* binary tree is said to be pseudo palindromic if at least one permutation of
* the node values in the path is a palindrome. return the number of pseudo
* palindromic paths going from the root node to leaf nodes.
*/
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int dfs(struct TreeNode *root, int *hash_table, int hash_size) {
hash_table[root->val]++;
if (!root->left && !root->right) {
int odd = 0;
for (int i = 0; i < hash_size; i++) {
if (hash_table[i] % 2) {
odd++;
if (odd > 1)
return 0;
}
}
return 1;
}
int left_cnt = 0, right_cnt = 0;
if (root->left) {
left_cnt = dfs(root->left, hash_table, hash_size);
hash_table[root->left->val]--;
}
if (root->right) {
right_cnt = dfs(root->right, hash_table, hash_size);
hash_table[root->right->val]--;
}
return left_cnt + right_cnt;
}
int pseudoPalindromicPaths(struct TreeNode *root) {
int hash_size = 10;
int *hash_table = calloc(hash_size, sizeof(int));
return dfs(root, hash_table, hash_size);
}
|