_2415. Reverse Odd Levels of Binary Tree.md

2415. Reverse Odd Levels of Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 23, 2024

Last updated : June 23, 2024

---

Related Topics : Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 78.36 %

---

Solutions

• m2415 v1 level order.py
• m2415 v2 2-Pass in order DFS.py

Python

m2415 v1 level order.py

# 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:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root or not root.left :  # we are promised that every level is filled
            return root

        level = 0
        nodes = (deque(), deque())

        nodes[0].append(root.left)
        nodes[0].append(root.right)

        while nodes[level] :
            if nodes[level][0].left and nodes[level][0].left.left :
                for node in nodes[level] :
                    nodes[(level + 1) % 2].append(node.left.left)
                    nodes[(level + 1) % 2].append(node.left.right)
                    nodes[(level + 1) % 2].append(node.right.left)
                    nodes[(level + 1) % 2].append(node.right.right)

            while nodes[level] :
                nodes[level][0].val, nodes[level][-1].val = nodes[level][-1].val, nodes[level][0].val
                nodes[level].popleft()
                nodes[level].pop()

            level = (level + 1) % 2

        return root

m2415 v2 2-Pass in order DFS.py

# 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:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        vals = []

        def firstPass(curr: Optional[TreeNode], level: int) -> None :
            if curr.left :
                firstPass(curr.left, level + 1)

            if level % 2 :
                vals.append(curr.val)

            if curr.left :
                firstPass(curr.right, level + 1)

        def secondPass(curr: Optional[TreeNode], level: int) -> None :
            if curr.left :
                secondPass(curr.left, level + 1)

            if level % 2 :
                curr.val = vals.pop()

            if curr.left :
                secondPass(curr.right, level + 1)


        firstPass(root, 0)
        secondPass(root, 0)

        return root