题目
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.
解题思路
递归，记录从根到叶节点每个数字出现次数的奇偶性，如果最多一个数字出现了奇数次，则可以构成一个伪回文路径
代码
class Solution:
def pseudoPalindromicPaths (self, root: TreeNode) -> int:
def dfs(node):
cur[node.val] = not cur[node.val]
if not(node.left or node.right):
if cur.count(False) <= 1:
res[0] += 1
cur[node.val] = not cur[node.val]
return
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
cur[node.val] = not cur[node.val]
res = [0]
cur = [True] * 10
dfs(root)
return res[0]
