226. Invert Binary Tree

# 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: TreeNode) -> TreeNode:
        # main idea: post order 
        def helper(node):  # can actually remove the helper function 
            #step1: base case:  when node == None 
            if node == None:
                return None 
            # step2: condition of swap: any of child node is not None,
            node.left,node.right = helper(node.right) ,helper(node.left)
            # step3: return parent node 
            return node
        return helper(root)

# main idea: BFS using queue 
# 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: TreeNode) -> TreeNode:
        # main idea: inorder 
        # step1: edge case => if root is empty
        if not root:
            return None
        #step2 initialize queue
        q = collections.deque()
        q.append(root)
        
        # step3: termination condition==> q is empty 
        while q:
            # inorder 
            # step4: get current node 
            cur = q.popleft()
            # step5: swap left right child 
            cur.left,cur.right = cur.right, cur.left
            # step6 append valid children into queue 
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)
        return root