1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def dfs(self, node, path):
9
        if not node:
10
            return
11

12
        if not node.left and not node.right:
13
            path += [node.val]
14
            d = {}
15
            for i in path.copy():
16
                if i in d:
17
                    del d[i]
18
                else:
19
                    d[i] = 1
20
            # print(d.items())
21
            self.ans += 1 if len(d) <= 1 else 0
22
            return
23

24
        self.dfs(node.left, path + [node.val])
25
        self.dfs(node.right, path + [node.val])
26

27
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
28
        self.ans = 0
29
        self.dfs(root, [])
30
        return self.ans