1
class Solution {
2
 private:
3
  void dfs(TreeNode *root, int &ans, unordered_map<int, int> &m) {
4
    if (!root) return;
5
    m[root->val]++;
6

7
    if (!root->left and !root->right) {
8
      int oddCnt = 0;
9
      for (auto it : m) {
10
        if (it.second % 2 != 0) oddCnt++;
11
      }
12
      if (oddCnt <= 1) ans++;
13
    }
14

15
    dfs(root->left, ans, m);
16
    dfs(root->right, ans, m);
17

18
    m[root->val]--;
19
  }
20

21
 public:
22
  int pseudoPalindromicPaths(TreeNode *root) {
23
    if (root == NULL) return 0;
24

25
    int ans = 0;
26

27
    unordered_map<int, int> m;
28

29
    dfs(root, ans, m);
30

31
    return ans;
32
  }
33
};