Please see github.com/anusha-murali for all of my repositories.
This is a simple problem from LeetCode (Problem #226).
Problem: 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]
Example 2:
Input: root = []
Output: []
Solution
We can implement a simple solution using recursion as follows
# 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 not root:
return root
temp = self.invertTree(root.left)
root.left = self.invertTree(root.right)
root.right = temp
return root
Runtime: Time complexity $O(n)$. Space complexity $O(n)$.