226-InvertBinaryTree

Inveret Binary Tree

Problem can be found in here!

# 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

Solution1: Depth-First Search(Recursion)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left, root.right = self.inverter(root.left, root.right)
        return root

    def inverter(self, left_child: Optional[TreeNode], right_child: Optional[TreeNode]) -> List[TreeNode]:
        if left_child is not None:
            left_child.left, left_child.right = self.inverter(left_child.left, left_child.right)
        if right_child is not None:
            right_child.left, right_child.right = self.inverter(right_child.left, right_child.right)

        return right_child, left_child

Time Complexity: , Space Complexity: for the recursive stack, where h is the height of the binary tree. In worst case, h will be n for an unbalanced binary tree.

Solution2: Improved Solution 1

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

Time Complexity: , Space Complexity: for the recursive stack, where h is the height of the binary tree. In worst case, h will be n for an unbalanced binary tree.