1
class Solution {
2
  public int pseudoPalindromicPaths(TreeNode root) {
3
    return helper(root, 0);
4
  }
5

6
  public int helper(TreeNode node, int freq) {
7
    if (node == null) return 0;
8

9
    freq = freq ^ (1 << node.val);
10
    if (node.left == null && node.right == null) {
11
      return (freq & (freq - 1)) == 0 ? 1 : 0;
12
      // return Integer.bitCount(freq) <= 1 ? 1 : 0;
13
    }
14
    return helper(node.left, freq) + helper(node.right, freq);
15
  }
16
}