# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.10.0 64-bit
#     name: python3
# ---

# # Invert Binary Tree
# Given the root of a binary tree, invert the tree, and return its root.
#
# ### Example 1:
# - Input: root = [4,2,7,1,3,6,9]
# - Output: [4,7,2,9,6,3,1]
# <table width="256px">
#   <tr>
#     <td><img src="../images/invert-binary-tree.png" /></td>
#   </tr>
# </table>
#
# ### Example 2
# - Input: root = [2,1,3]
# - Output: [2,3,1]
#
# ### Example 2
# - Input: root = []
# - Output: []
#
# ### Constraints:
# - The number of nodes in the tree is in the range [0, 100].
# - -100 <= Node.val <= 100
#
# ## Solution

# +
# 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:
    '''
    IDEA:
        Traverse tree, and for each node change 
        the order of left and right nodes
    '''
    def invertTree(self, root: TreeNode) -> TreeNode:
        def _post_order(node):
            if not node:
                return None
            else:
                node.left, node.right = node.right, node.left   
                _post_order(node.left)
                _post_order(node.right)
            return node
            
        return _post_order(root)
# -

# ## Analysis
# - Time Complexity: O(n)
# - Space Complexity: O(1)

StarcoderdataJupyterScriptsDedupFiltered