Invert Binary Tree

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• For recursion, notice that you just have to swap the left and right nodes, and the rest will sort itself out.

Code

Recursive

# 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 None
        root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)
        return root

Iterative

# 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 None
 
        queue = []
        
        if root.left:
            queue.append(root.left)
        else:
            queue.append(None)
        if root.right:
            queue.append(root.right)
        else:
            queue.append(None)
 
        values = []
        while queue != []:
            node = queue.pop(0)
            if node:
                values.append(node.val)
            else:
                values.append(None)
                continue
 
            if node.left:
                queue.append(node.left)
            else:
                queue.append(None)
 
            if node.right:
                queue.append(node.right)
            else:
                queue.append(None)
 
        queue = [root]
            
        while queue != []:
            node = queue.pop(0)
            if node == None:
                continue
            
            val = values.pop(0)
            if val == None:
                node.right = None
            else:
                if node.right:
                    node.right.val = val
                else:
                    dummy = TreeNode(val)
                    node.right = dummy
            
            queue.append(node.right)
 
            val = values.pop(0)
            if val == None:
                node.left = None
            else:
                if node.left:
                    node.left.val = val
                else:
                    dummy = TreeNode(val)
                    node.left = dummy
            
            queue.append(node.left)
 
        return root

Notes

Cards

START Basic Front: Invert Binary Tree Back: root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)

END

---

References

Invert Binary Tree