Loading problem...
You are given a binary tree where each node contains a single digit value between 1 and 9 (inclusive). A root-to-leaf path in this tree is considered rearrangeable into a palindrome if the sequence of node values along that path can be reordered to form a palindrome.
A palindrome is a sequence that reads the same forwards and backwards (e.g., "323", "121", "7"). Note that the actual node values along the path do not need to form a palindrome directly—what matters is whether some permutation of those values could form one.
Your task is to count and return the total number of root-to-leaf paths in the tree that satisfy this rearrangeability property.
Key Insight: A sequence of characters (or digits) can be rearranged into a palindrome if and only if at most one character appears an odd number of times. For sequences of even length, every character must appear an even number of times. For sequences of odd length, exactly one character can appear an odd number of times (this character would be placed in the middle).
root = [2,3,1,3,1,null,1]2The binary tree has three root-to-leaf paths: Path [2→3→3] contains digits {2, 3, 3} which can be rearranged to '323' (a palindrome). Path [2→1→1] contains digits {2, 1, 1} which can be rearranged to '121' (a palindrome). Path [2→1→1] (right subtree) contains digits {2, 1, 1} which can also be rearranged to '121'. However, the path [2→3→1] contains {2, 3, 1} and cannot form a palindrome as all three digits appear exactly once. Thus, 2 paths satisfy the condition.
root = [2,1,1,1,3,null,null,null,null,null,1]1There are three root-to-leaf paths in this tree. The path [2→1→1] contains {2, 1, 1} and can form palindrome '121'. The path [2→1→3→1] contains {2, 1, 3, 1} which has two digits (2 and 3) appearing an odd number of times, so it cannot form a palindrome. The path [2→1] only exists if that node is a leaf. Only one path satisfies the rearrangeable palindrome property.
root = [9]1The tree consists of a single node with value 9. This single-node path trivially forms a palindrome '9', so there is exactly 1 valid path.
Constraints