1457

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 class Solution {
public:
void findPaths(TreeNode* root, unordered_map<int, int>& pathCounts, int& res) {
    if (root == nullptr) {
        return;
    }

    pathCounts[root->val]++;

    if (root->left == nullptr && root->right == nullptr) {      //leaf mil gayi
        int oddCount = 0; 
        for (const auto& entry : pathCounts) {
            if (entry.second % 2 == 1) {
                oddCount++;
            }
        }
        if (oddCount <= 1) {
            res++;
        }
    }

    findPaths(root->left, pathCounts, res);
    findPaths(root->right, pathCounts, res);

    pathCounts[root->val]--;

    if (pathCounts[root->val] == 0) {
        pathCounts.erase(root->val);
    }
}

int pseudoPalindromicPaths(TreeNode* root) {
    int res = 0;
    vector<vector<int>> paths;
    unordered_map<int, int>pathCounts;
   findPaths(root,pathCounts,res);

    return res;
}

};