Input: root =[2,3,5,8,13,21,34]Output: [2,5,3,8,13,21,34]Explanation:
The tree has only one odd level.The nodes at level 1 are 3,5 respectively, which are reversed and become 5,3.
Input: root =[7,13,11]Output: [7,11,13]Explanation:
The nodes at level 1 are 13,11, which are reversed and become 11,13.
Example 3:
1
2
3
4
5
6
Input: root =[0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]Explanation:
The odd levels have non-zero values.The nodes at level 1 were 1,2, and are 2,1 after the reversal.The nodes at level 3 were 1,1,1,1,2,2,2,2, and are 2,2,2,2,1,1,1,1 after the reversal.
Constraints:
The number of nodes in the tree is in the range [1, 214].
To reverse the node values at each odd level of a perfect binary tree, we can perform a level-order traversal (BFS - Breadth-First Search) while keeping track of the nodes at each level. For each odd level, we reverse the node values.
Here is the approach:
Perform a BFS traversal to access nodes level by level.
Store the nodes at each level.
For each odd level, reverse the values of the nodes.
Assign the reversed values back to the corresponding nodes.