LeetCode 2415 Reverse Odd Levels of Binary Tree

Table of contents

Description

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.

Hint 1

Try to solve recursively for each level independently.

Hint 2

While performing a depth-first search, pass the left and right nodes (which should be paired) to the next level. If the current level is odd, then reverse their values, or else recursively move to the next level.

Idea

We could use dfs to traverse the tree.

1. Because we need to be able to reverse, i.e., to swap the values of two nodes, we need access to the two nodes. From the root node, we could traverse to the left and right child.
2. We use a d (depth) variable to track how deep we have traveled from the root.
3. If the depth is odd, we perform a swap.
4. We recursively traverse to the next level by visiting the children nodes of the two currently being visited nodes in mirror.

Complexity: Time $O(n)$, Space $O(\log n)$.

Python

class Solution:
    """11 ms, 22.92 mb"""

    def reverseOddLevels(self, root) -> TreeNode:
        def dfs(l, r, d):
            if l is None or r is None: return
            if d % 2 == 1: l.val, r.val = r.val, l.val
            dfs(l.left, r.right, d + 1)
            dfs(l.right, r.left, d + 1)

        dfs(root.left, root.right, 1)
        return root

Java

// DFS. O(n) time, O(log n) space.
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1);
        return root;
    }

    private void dfs(TreeNode l, TreeNode r, int d) {
        if (l == null || r == null) return;
        if (d % 2 == 1) {
            int temp = l.val;
            l.val = r.val;
            r.val = temp;
        }
        dfs(l.left, r.right, d + 1);
        dfs(l.right, r.left, d + 1);
    }
}

C++

// leet 2415, DFS. O(n) time, O(log n) space.
class Solution2415 {
public:
    TreeNode *reverseOddLevels(TreeNode *root) {
        if (root) dfs(root->left, root->right, 1);
        return root;
    }

private:
    void dfs(TreeNode *l, TreeNode *r, int d) {
        if (!l || !r) return;
        if (d % 2 == 1) swap(l->val, r->val);
        dfs(l->left, r->right, d + 1);
        dfs(l->right, r->left, d + 1);
    }
};

Rust

impl Solution {
    pub fn reverse_odd_levels(root: TreeNodeRef) -> TreeNodeRef {
        if let Some(ref node) = root {
            let node = node.borrow();
            Self::dfs(&node.left, &node.right, 1);
        }
        root
    }

    fn dfs(l: &TreeNodeRef, r: &TreeNodeRef, d: i32) {
        match (l, r) {
            (Some(left), Some(right)) => {
                if d % 2 == 1 {
                    let mut lb = left.borrow_mut();
                    let mut rb = right.borrow_mut();
                    std::mem::swap(&mut lb.val, &mut rb.val);
                }
                let lb = left.borrow();
                let rb = right.borrow();
                Self::dfs(&lb.left, &rb.right, d + 1);
                Self::dfs(&lb.right, &rb.left, d + 1);
            }
            _ => {}
        }
    }
}