Pseudo-Palindromic Paths in a Binary Tree

lcpy gen -n 1457   # by problem number
lcpy gen -s pseudo_palindromic_paths_in_a_binary_tree   # by problem name

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 the red path and the 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).

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

Input: root = [9]
Output: 1

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h)
    def pseudo_palindromic_paths(self, root: TreeNode[int] | None) -> int:
        if root is None:
            return 0
        total = 0
        stack: list[tuple[TreeNode[int], int]] = [(root, 1 << root.val)]
        while stack:
            node, mask = stack.pop()
            if node.left is None and node.right is None:
                if mask & (mask - 1) == 0:
                    total += 1
                continue
            if node.left is not None:
                stack.append((node.left, mask ^ (1 << node.left.val)))
            if node.right is not None:
                stack.append((node.right, mask ^ (1 << node.right.val)))
        return total