2415. Reverse Odd Levels of Binary Tree LeetCode Solution

In this guide, you will get 2415. Reverse Odd Levels of Binary Tree LeetCode Solution with the best time and space complexity. The solution to Reverse Odd Levels of Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Reverse Odd Levels of Binary Tree solution in C++
Reverse Odd Levels of Binary Tree solution in Java
Reverse Odd Levels of Binary Tree solution in Python
Additional Resources

2415. Reverse Odd Levels of Binary Tree LeetCode Solution image

Problem Statement of Reverse Odd Levels of Binary Tree

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

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

Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.

Example 1:

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.

Example 2:

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:

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].
0 <= Node.val <= 105
root is a perfect binary tree.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

2415. Reverse Odd Levels of Binary Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* reverseOddLevels(TreeNode* root) {
    dfs(root->left, root->right, true);
    return root;
  }

 private:
  void dfs(TreeNode* left, TreeNode* right, bool isOddLevel) {
    if (left == nullptr)
      return;
    if (isOddLevel)
      swap(left->val, right->val);
    dfs(left->left, right->right, !isOddLevel);
    dfs(left->right, right->left, !isOddLevel);
  }
};
/* code provided by PROGIEZ */

2415. Reverse Odd Levels of Binary Tree LeetCode Solution in Java

class Solution {
  public TreeNode reverseOddLevels(TreeNode root) {
    dfs(root.left, root.right, true);
    return root;
  }

  private void dfs(TreeNode left, TreeNode right, boolean isOddLevel) {
    if (left == null)
      return;
    if (isOddLevel) {
      final int val = left.val;
      left.val = right.val;
      right.val = val;
    }
    dfs(left.left, right.right, !isOddLevel);
    dfs(left.right, right.left, !isOddLevel);
  }
}
// code provided by PROGIEZ

2415. Reverse Odd Levels of Binary Tree LeetCode Solution in Python

class Solution:
  def reverseOddLevels(self, root: TreeNode | None) -> TreeNode | None:
    def dfs(left: TreeNode | None, right: TreeNode | None, isOddLevel: bool) -> None:
      if not left:
        return
      if isOddLevel:
        left.val, right.val = right.val, left.val
      dfs(left.left, right.right, not isOddLevel)
      dfs(left.right, right.left, not isOddLevel)

    dfs(root.left, root.right, True)
    return root
 # code by PROGIEZ