226. Invert Binary Tree

Easy

Problem:

Invert the binary tree based on the center.

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

https://leetcode.com/problems/invert-binary-tree/

Solution:

Pythonic way

For reference, the last "return None" can be omitted. While languages like Java or C++ would throw an error if nothing is returned, Python assigns None by default.

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

BFS/DFS

Previously, the recursive solution was a bottom-up approach that descends to the furthest leaf nodes and backtracks while swapping. In contrast, this solution is a top-down approach that starts from the parent node, swaps, and continues descending downward.

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dq = collections.deque([root])
        while dq:
            # BFS
            node = dq.popleft() # DFS -> dq.pop()
            
            if node:
                # Pre-Order Traversal
                node.left, node.right = node.right, node.left

                dq.append(node.left)
                dq.append(node.right)

        return root

Post-Order Traversal

All you need to do is change the order of traversal.

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dq = collections.deque([root])
        while dq:
            # BFS
            node = dq.popleft() # DFS -> dq.pop()
            
            if node:
                dq.append(node.left)
                dq.append(node.right)
                
                # Post-Order Traversal
                node.left, node.right = node.right, node.left

        return root