Reverse the left-to-right order of node values at every odd-numbered level of the perfect binary tree. Return the root after these changes.
The root is at level 0. Values on even-numbered levels stay in their original positions. Change node values without changing parent-child links.
A perfect binary tree has two children at every non-leaf node, and all leaves occur at the same level. Examples show trees as level-order arrays: the root first, then each successive level from left to right.
Example 1:
Input: root = [9,1,7,2,3,4,5]
Output: [9,7,1,2,3,4,5]Explanation: Level 1 changes from [1,7] to [7,1]. The root and level 2 are even-numbered levels, so their values stay unchanged.
Example 2:
Input: root = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
Output: [1,3,2,4,5,6,7,15,14,13,12,11,10,9,8]Explanation: Level 1 changes from [2,3] to [3,2]. Level 3 changes from [8,9,10,11,12,13,14,15] to [15,14,13,12,11,10,9,8]. Levels 0 and 2 are unchanged.
Example 3:
Input: root = [0]
Output: [0]Explanation: The tree has only level 0. There are no odd-numbered levels to reverse, so the single node remains 0.
Constraints:
- The tree contains between 1 and 16384 nodes.
0 <= Node.val <= 100000- The input tree is perfect.