Reverse Odd Levels of Binary Tree

Leetcode Problem:

• Reverse Odd Levels of Binary Tree

Summary

• Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.

Approach

• The approach used is to first initialize a tree array with the values of the nodes in the binary tree
• Then, a recursive function is used to reverse the values at each odd level
• The function checks if the current index is greater than the maximum size, and if so, returns
• Otherwise, it checks if the level is odd, and if so, reverses the values at the current index and the next index
• Finally, the function is called recursively for the left and right subtrees.

Complexity

• O(n log n) where n is the number of nodes in the tree, due to the recursive calls and the reversal operation at each odd level.

Explanation

• The provided solution code first initializes a tree array with the values of the nodes in the binary tree using the init function
• Then, it calls the reverse function to reverse the values at each odd level
• The reverse function checks if the current index is greater than the maximum size, and if so, returns
• Otherwise, it checks if the level is odd, and if so, reverses the values at the current index and the next index
• Finally, the function is called recursively for the left and right subtrees
• The changeValue function is used to update the values of the nodes in the binary tree after reversing the values at each odd level.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    const static int TREE_SIZE = (1<<14) + 1;
    int tree[TREE_SIZE];
    int maxSize = 0;
    void init(TreeNode* root, int idx){
        if(root == nullptr){
            return;
        }
        maxSize = (maxSize, idx);
        tree[idx] = root->val;
        init(root->left, idx*2);
        init(root->right, idx*2 + 1);
    }
    void reverse(int level, int idx){
        if(idx > maxSize) return;
        int idx2 = idx << 1;
        if(level & 1){
            int l = idx;
            int r = idx2 - 1;
            while(l < r){
                int t = tree[l];
                tree[l] = tree[r];
                tree[r] = t;
                l++;
                r--;
            }
        }
        reverse(level+1, idx2);
    }
    TreeNode* changeValue(TreeNode* root, int idx){
        if(root == nullptr) return nullptr;
        root->val = tree[idx];
        changeValue(root->left, idx*2);
        changeValue(root->right, idx*2 + 1);
        return root;
    }
    TreeNode* reverseOddLevels(TreeNode* root) {
        init(root, 1);
        reverse(0, 1);
        return changeValue(root, 1);
    }
};