<p>Given the <code>root</code> of a <strong>perfect</strong> binary tree, reverse the node values at each <strong>odd</strong> level of the tree.</p>

<ul>
	<li>For example, suppose the node values at level 3 are <code>[2,1,3,4,7,11,29,18]</code>, then it should become <code>[18,29,11,7,4,3,1,2]</code>.</li>
</ul>

<p>Return <em>the root of the reversed tree</em>.</p>

<p>A binary tree is <strong>perfect</strong> if all parent nodes have two children and all leaves are on the same level.</p>

<p>The <strong>level</strong> of a node is the number of edges along the path between it and the root node.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/07/28/first_case1.png" style="width: 626px; height: 191px;" />
<pre>
<strong>Input:</strong> root = [2,3,5,8,13,21,34]
<strong>Output:</strong> [2,5,3,8,13,21,34]
<strong>Explanation:</strong> 
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/07/28/second_case3.png" style="width: 591px; height: 111px;" />
<pre>
<strong>Input:</strong> root = [7,13,11]
<strong>Output:</strong> [7,11,13]
<strong>Explanation:</strong> 
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
<strong>Output:</strong> [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
<strong>Explanation:</strong> 
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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 2<sup>14</sup>]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
	<li><code>root</code> is a <strong>perfect</strong> binary tree.</li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    levels = 0
    total_elements = 0
    plain_array = []

    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        
        self.convert_to_array(root)
        self.reverse_odd_levels()
        tree = self.build_tree()

        return tree
    
    def convert_to_array(self, root: TreeNode):
        self.levels = self.get_number_of_levels(root)
        self.total_elements = self.get_number_of_elements(self.levels)
        self.plain_array = [0] * self.total_elements 
        self.put_node_to_array(root, offset_inside_level = 0, elements_on_this_level = 1, total_elements = 0)

    def get_number_of_levels(self, node: TreeNode) -> int:
        current_node = node
        levels = 0

        # only ideal binary trees supported
        while current_node is not None:
            levels += 1
            current_node = current_node.left

        return levels
    
    def get_number_of_elements(self, levels: int) -> int:
        current_level = 1
        current_level_elements = 1
        total_elements = 0

        # 1 + 2 + 4 + 8 + 16 ... 
        while current_level <= levels:
            total_elements += current_level_elements
            current_level += 1
            current_level_elements *= 2
            
        return total_elements

    def put_node_to_array(self
                          , current_node: Optional[TreeNode]
                          , offset_inside_level: int
                          , elements_on_this_level: int
                          , total_elements: int
                          ):
        
        # can't continue if the node is empty
        if current_node is None:
            return

        # make sure that array has this amount of items
        item_index = total_elements + offset_inside_level

        self.plain_array[item_index] = current_node.val
        total_elements += elements_on_this_level # total elements is increased
        elements_on_this_level *= 2 # next level has twice as much nodes
        offset_inside_level *= 2
        self.put_node_to_array(current_node.left, offset_inside_level + 0, elements_on_this_level, total_elements)
        self.put_node_to_array(current_node.right, offset_inside_level + 1, elements_on_this_level, total_elements)

    def reverse_odd_levels(self):
        level = 1
        elements_on_this_level = 1
        current_offset = 0
        total_elements = len(self.plain_array)

        while current_offset < total_elements:
            # revert odd levels
            if level % 2 == 0 and level > 1:
                start_index = current_offset
                end_index = current_offset + elements_on_this_level - 1
                self.reverse(start_index, end_index)

            current_offset += elements_on_this_level
            elements_on_this_level *= 2
            level += 1

    def reverse(self, start_index: int, end_index: int):
        while start_index < end_index:
            left = self.plain_array[start_index]
            right = self.plain_array[end_index]
            self.plain_array[start_index] = right
            self.plain_array[end_index] = left
            start_index += 1
            end_index -= 1

    def build_tree(self) -> TreeNode:
        return self.get_node_from_list(offset_inside_level = 0, elements_on_this_level = 1, total_elements = 0)
    
    def get_node_from_list(self
                           , offset_inside_level: int
                           , elements_on_this_level: int
                           , total_elements: int
                           ) -> Optional[TreeNode]:
        root_index = total_elements + offset_inside_level

        if len(self.plain_array) <= root_index:
            return None
        
        root_value = self.plain_array[root_index]

        offset_inside_next_level = offset_inside_level * 2
        elements_on_next_level = elements_on_this_level * 2
        total_elements_next_level = total_elements + elements_on_this_level
        left_child = self.get_node_from_list(offset_inside_next_level + 0, elements_on_next_level, total_elements_next_level)
        right_child = self.get_node_from_list(offset_inside_next_level + 1, elements_on_next_level, total_elements_next_level)

        return TreeNode(root_value, left_child, right_child)


754