Pseudo-Palindromic Paths in a Binary Tree

Given the root of a binary tree, return the number of root-to-leaf paths where the multiset of node values along the path can be rearranged to form a palindrome. Pattern focus: Root To Leaf Paths. Track the parity of each digit count along the current path.

Input Format

root = binary tree root

Output Format

number of pseudo-palindromic root-to-leaf paths

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [2,3,1,3,1,null,1]

Output:

2

Explanation:

Two root-to-leaf paths can be rearranged into a palindrome.

Example 2:

Input:

root = [2,1,1]

Output:

0

Explanation:

Neither root-to-leaf path has at most one odd count.

Loading...
Pseudo-Palindromic Paths in a Binary Tree