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.

&nbsp;
Example 1:



Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 2:



Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 3:

Input: root = [9]
Output: 1


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 105].
	1 &lt;= Node.val &lt;= 9


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, node, path):
        if not node:
            return
        
        if not node.left and not node.right:
            path += [node.val]
            d = {}
            for i in path.copy():
                if i in d:
                    del d[i]
                else:
                    d[i] = 1
            #print(d.items())
            self.ans += 1 if len(d) <= 1 else 0
            return
                
        self.dfs(node.left, path+[node.val])
        self.dfs(node.right, path+[node.val])
    
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        self.dfs(root, [])
        return self.ans
class Solution {
    public int pseudoPalindromicPaths (TreeNode root) {
        return helper(root, 0);
    }
    
    public int helper(TreeNode node, int freq) {
        if (node == null) return 0;
        
        freq = freq ^ (1 << node.val);
        if (node.left == null && node.right == null) {
            return (freq & (freq - 1)) == 0 ? 1 : 0;
            // return Integer.bitCount(freq) <= 1 ? 1 : 0;
        }
        return helper(node.left, freq) + helper(node.right, freq);
    }
}
class Solution {
private:
	void dfs(TreeNode* root,int &ans,unordered_map<int,int> &m){

		if(!root) return;
		m[root -> val]++;

		if(!root -> left and !root -> right){
			int oddCnt = 0;
			for(auto it : m){
				if(it.second % 2 != 0) oddCnt++;
			}
			if(oddCnt <= 1) ans++;
		}


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

		m[root -> val]--;

	}
public:
	int pseudoPalindromicPaths (TreeNode* root) {

		if(root == NULL) return 0;

		int ans = 0;

		unordered_map<int,int> m;

		dfs(root,ans,m);

		return ans;

	}
};
var pseudoPalindromicPaths  = function(root) {
    if(!root) return 0;
    // if even it's zero or it's power of two when odd
    const ways = (r = root, d = 0) => {
        if(!r) return 0;
        d = d ^ (1 << r.val);
        // leaf
        if(r.left == r.right && r.left == null) {
            const hasAllEven = d == 0;
            const hasOneOdd = (d ^ (d & -d)) == 0;
            return Number(hasEven || hasOneOdd);
        }
        return ways(r.left, d) + ways(r.right, d);
    }
    return ways();
};
Pseudo-Palindromic Paths in a Binary Tree