# 1457. Pseudo-Palindromic Paths in a Binary Tree """ 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. """ # Definition for a binary tree node. class TreeNode(object): def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution(object): def pseudoPalindromicPaths(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 count ^= 1 << (root.val - 1) res = self.pseudoPalindromicPaths( root.left, count ) + self.pseudoPalindromicPaths(root.right, count) if root.left == root.right: if count & (count - 1) == 0: res += 1 return res if __name__ == "__main__": obj = Solution() print(obj.pseudoPalindromicPaths(root=[2, 3, 1, 3, 1, null, 1])) print( obj.pseudoPalindromicPaths( root=[2, 1, 1, 1, 3, null, null, null, null, null, 1] ) ) print(obj.pseudoPalindromicPaths(root=[9]))