Pseudo-Palindromic Paths in a Binary Tree
medium
binary-tree
depth-first-search
bit-manipulation
Given the root of a binary tree where each node stores a digit from 1 to 9, a root-to-leaf path is called pseudo-palindromic if you can rearrange the digits on that path to form a palindrome.
A sequence can be rearranged into a palindrome when at most one digit appears an odd number of times.
Return the number of pseudo-palindromic root-to-leaf paths.
Input / output
- Input:
root: TreeNode(JSON test fixture is a LeetCode-style level-order array, e.g.[2,3,1,3,1,null,1], withnullfor a missing child) - Output:
int
Constraints
- 0 <= number of nodes <= 100,000
- 1 <= node.val <= 9
Follow-up
How would you adapt the solution if values were not limited to digits 1 through 9, so a fixed 9-bit mask was no longer enough?
Examples
Example 1
Input: root = [2,3,1,3,1,null,1]
Output: 2
Example 2
Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Example 3 (empty tree)
Input: root = []
Output: 0
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.