Invert Binary Tree - Leetcode Python Solution

 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) 

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...