933. Pseudo-Palindromic Paths in Binary Tree

Given the root of a binary tree whose node values are digits 1 through 9, a root-to-leaf path is pseudo-palindromic if at least one permutation of its values reads the same forwards and backwards. Return the number of pseudo-palindromic root-to-leaf paths. The tree is given as a level-order array.

Input: A level-order array of the tree (values 1-9).

Output: Integer — the count of pseudo-palindromic paths.

Examples

Input: [2,3,1,3,1,null,1]
Output: 2
Explanation: Two paths can form palindromes.

Input: [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: One qualifying path.

Input: [9]
Output: 1
Explanation: Single-node path is trivially palindromic.

Constraints

• 1<=nodes<=10^5
• 1<=value<=9

Asked by