Pseudo-Palindromic Paths in a Binary Tree

Count the paths from the root to a leaf whose node values can be rearranged into a palindrome. A palindrome reads the same forward and backward. Each path includes both its root and its leaf, and a leaf has no children.

Only the ability to rearrange a path's values matters; the values do not have to form a palindrome in their original order. Count each qualifying root-to-leaf path separately, even if different paths have the same values.

Examples use level-order arrays. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.

Example 1:

Input: root = [4,2,4,2,3,null,4]

Output: 2

Explanation: The paths [4,2,2] and [4,4,4] can form palindromes: 2,4,2 and 4,4,4. The remaining path [4,2,3] has three distinct values and cannot form a palindrome, so the answer is 2.

Example 2:

Input: root = [1,2,3]

Output: 0

Explanation: The two root-to-leaf paths are [1,2] and [1,3]. Each has two different values, so neither can be rearranged into a palindrome.

Example 3:

Input: root = [8]

Output: 1

Explanation: The only path contains the single value 8. A one-value sequence is already a palindrome.

Constraints:

• The tree contains between 1 and 100000 nodes.
• 1 <= Node.val <= 9