494. Almost Palindromic Routes
The hallways of a museum form a binary tree rooted at root. Every room carries a display code, a single digit stored in val. A tour starts at the root room and ends at a leaf room, which is a room with no children. Reading the codes of the rooms visited, in order, gives a sequence of digits.
A tour is called mirror-friendly if its digits can be rearranged to form a palindrome. Return how many tours from the root to a leaf are mirror-friendly. If root is empty there are no tours and the answer is 0.
Example 1
- Input:
- root = [2,3,1,3,1,null,1]
- Output:
- 2
- Explanation:
The tours 2-3-3 and 2-1-1 can be rearranged into palindromes (3-2-3 and 1-2-1), while 2-3-1 cannot, so the answer is 2.
Example 2
- Input:
- root = [5,2,2,null,null,2,6]
- Output:
- 1
- Explanation:
Only the tour 5-2-2 works (2-5-2); 5-2 and 5-2-6 have too many digits with odd counts, so the answer is 1.
Constraints
0 ≤ number of nodes ≤ 105
1 ≤ Node.val ≤ 9
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)