Approach: DFS with a 9-bit parity mask; palindrome iff at most one odd count

def pseudoPalindromicPaths(self, root):
    self.cnt = 0
    def dfs(node, mask):
        if not node: return
        mask ^= (1 << node.val)
        if not node.left and not node.right:
            if mask & (mask - 1) == 0: self.cnt += 1
            return
        dfs(node.left, mask); dfs(node.right, mask)
    dfs(root, 0)
    return self.cnt

Complexity: O(n) time, O(h) space.

Full Solution — all languages

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pseudoPalindromicPaths(self, root):
        self.cnt = 0
        def dfs(node, mask):
            if not node: return
            mask ^= (1 << node.val)
            if not node.left and not node.right:
                if (mask & (mask - 1)) == 0: self.cnt += 1
                return
            dfs(node.left, mask); dfs(node.right, mask)
        dfs(root, 0)
        return self.cnt

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int pseudoPalindromicPaths(TreeNode root) {
        cnt = 0;
        dfs(root, 0);
        return cnt;
    }
    int cnt;
    private void dfs(TreeNode node, int mask) {
        if (node == null) return;
        mask ^= (1 << node.val);
        if (node.left == null && node.right == null) {
            if ((mask & (mask - 1)) == 0) cnt++;
            return;
        }
        dfs(node.left, mask);
        dfs(node.right, mask);
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int pseudoPalindromicPaths(TreeNode* root) {
        int cnt = 0;
        function<void(TreeNode*,int)> dfs = [&](TreeNode* node, int mask) {
            if (!node) return;
            mask ^= (1 << node->val);
            if (!node->left && !node->right) {
                if ((mask & (mask - 1)) == 0) cnt++;
                return;
            }
            dfs(node->left, mask);
            dfs(node->right, mask);
        };
        dfs(root, 0);
        return cnt;
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {number}
 */ var pseudoPalindromicPaths = function(root) {
    let cnt = 0;
    const dfs = (node, mask) => {
        if (!node) return;
        mask ^= (1 << node.val);
        if (!node.left && !node.right) {
            if ((mask & (mask - 1)) === 0) cnt++;
            return;
        }
        dfs(node.left, mask);
        dfs(node.right, mask);
    };
    dfs(root, 0);
    return cnt;
};

Pseudo-Palindromic Paths in a Binary Tree

Example 1

Example 2

Constraints