5418_Pseudo-Palindromic-Paths.py

'''
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.

Example 1:
Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:
Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:
Input: root = [9]
Output: 1

Constraints:
The given binary tree will have between 1 and 10^5 nodes.
Node values are digits from 1 to 9.

'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def check_palindrome(self, table):
        odd_count = 0
        for num in table:
            if num %2 == 1:
                odd_count += 1
            if odd_count >= 2:
                return False
        return True
    def dfs(self, node, table):
        # if leaf node
        table[node.val - 1] += 1
        res = 0
        if node.left is None and node.right is None:
            res += 1 if self.check_palindrome(table) else 0
        if node.left is not None:
            res += self.dfs(node.left, table)
        if node.right is not None:
            res += self.dfs(node.right, table)
        table[node.val - 1] -= 1
        return res
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        table = [0 for _ in range(9)]  # count for 1-9
        return self.dfs(root, table)

s = Solution()
nums = [0,1,2,3,4]
index = [0,1,2,2,1]
res = s.createTargetArray(nums, index)
print(res)