[Leetcode] 226. Invert Binary Tree

Problem Link: https://leetcode.com/problems/invert-binary-tree/

Invert Binary Tree - LeetCode

 

Solution 1. Recursion (DFS)

Time: $O(N)$

Space: $O(1)$ 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # None
        if root is None:
            return None
        else:
            # Invert
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root

Solution 2. Stack (DFS)

Time: $O(N)$

from collections import deque

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return None

        q = deque(); q.append(root)
        while q:
            node = q.pop()
            node.left, node.right = node.right, node.left
            
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            
        return root

Solution 3. Queue (BFS)

Time: $O(N)$

from collections import deque

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return None
        
        q = deque(); q.append(root)
        while q:
            node = q.popleft()
            node.left, node.right = node.right, node.left

            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            
        return root