Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Iterative approcah .
# 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:
if not root:
return None
q = []
q.append(root)
while q:
curr = q.pop()
curr.left , curr.right = curr.right,curr.left
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
return root
TC: O(n)
SC: O(n) in worst case where queue is completely occupied.
Recursive approch:
# 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:
if not root:
return None
curr = root
if curr.left:
self.invertTree(curr.left)
if curr.right:
self.invertTree(curr.right)
curr.left,curr.right = curr.right,curr.left
return root
Recursive approach:
# 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:
if not root:
return None
curr = root
curr.left,curr.right = curr.right,curr.left
if curr.left:
self.invertTree(curr.left)
if curr.right:
self.invertTree(curr.right)
return root
TC: O(n)
SC: O(n)
