1. Problem
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