Pseudo-Palindromic Paths in a Binary Tree

Comparing my code from a year ago.

Sep 14, 2022

temp = []
d={}
ans = 0
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:



        def goDeep(node):

            global temp,d,ans


            if node:

                temp.append(node.val)

                if node.val in d:
                    d[node.val] = d[node.val] + 1
                else:
                    d[node.val] = 1

                if node.left:
                    goDeep(node.left)



                if node.right:
                    goDeep(node.right)


                l = len(temp)
                if not node.left and not node.right :


                    s = sum(value % 2 != 0 for value in d.values())

                    if l%2==0:
                        if s==0:
                            ans=ans+1
                    else:
                        if s==1:
                            ans=ans+1


                if l > 0:
                    deletedVal = temp.pop()
                    d[deletedVal] = d[deletedVal] - 1


        global d,temp,ans

        ans = 0 
        d = {}
        temp = []

        goDeep(root)


        return ans

---

Jan 24, 2024

# 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 pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        '''
        Get paths from root to leafs
        Check if path can be palindrome
            - Odd : Every digit must occur evenly - except 1
            - Even : Every digit must occur - evenly
        '''

        def isPalindrome(count):
            odds = 0
            total = 0

            for e in count.values():
                total += e
                if e % 2 != 0:
                    odds += 1

            if total % 2 != 0:
                odds -= 1

            return odds == 0

        def traverse(node, count):
            nonlocal ans
            if node:
                count[node.val] += 1

                if not node.left and not node.right:
                    if isPalindrome(count):
                        ans += 1

                traverse(node.left, count)
                traverse(node.right, count)

                count[node.val] -= 1

        ans = 0
        traverse(root, defaultdict(int))
        return ans