给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1：
输入：root = [2,3,1,3,1,null,1]
输出：2
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
示例 2：
输入：root = [2,1,1,1,3,null,null,null,null,null,1]
输出：1
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。
示例 3：
输入：root = [9]
输出：1
提示：
给定二叉树的节点数目在 1 到 10^5 之间。
节点值在 1 到 9 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一种思路：
怎么判断一个路径是不是伪回文路径呢？
如果一个路径里的所有数，最多只有一个数出现次数为奇数次，那么这个路径就是伪回文路径。
所以此题等价于找到二叉树的所有路径，然后判断路径里每个元素出现次数的问题。
时间复杂度：O（N）
空间复杂度：O（N）
class Solution(object):
def pseudoPalindromicPaths (self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 0
def dfs(node, path):
if not node:
return
path = path + [node.val]
if not node.left and not node.right:
if self.hasPalindromic(path):
self.res += 1
dfs(node.left, path)
dfs(node.right, path)
dfs(root, [])
return self.res
def hasPalindromic(self, nums):
from collections import Counter
dic = Counter(nums)
oddCnt = 0
for val in dic.values():
if val % 2:
oddCnt += 1
return oddCnt <= 1第二种思路：
题目里其实给出了节点的值只有 1 – 9 这个条件，所以可以有一个小优化，
把之前的 path 改成一个长度为 9 的数组，
每次遍历到一个新的节点，就把对应下表上的值 + 1，
判断伪回文时，就遍历该数组，看是不是值为奇数的下标最多只有一个。
比较简单，没有实现。