# [leetcode] 226. Invert Binary Tree _ Algorithm Problem Solve for python

## 1. Problem

226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.


Given n, calculate F(n).

Example 1:

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


Example 2:

Input: root = [2,1,3]
Output: [2,3,1]


Example 3:

Input: root = []
Output: []


Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

## 2. Solution

I solved this problem like this.

### 2.1. Using queue

I use python deque.

• Complexity
• Time complexity : O(N)
• Space complexity : O(1)
• Step
• Pop node no deque and put node’s left and right on deque.
# 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
from collections import deque

class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return

queue = deque([root])
while len(queue) > 0:
this_node = queue.popleft()
for x in [this_node.left, this_node.right]:
if x:
queue.append(x)
this_node.left, this_node.right = this_node.right, this_node.left

return root


### 2.2. Using recursion

Other user solve this problem like this.

• Complexity
• Time complexity : O(N)
• Space complexity : O(1)
• Step
• Pop node no deque and put node’s left and right on deque.
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: #Base Case
return root
self.invertTree(root.left) #Call the left substree
self.invertTree(root.right)  #Call the right substree
# Swap the nodes
root.left, root.right = root.right, root.left
return root # Return the root