0226. Invert Binary Tree

0226. Invert Binary Tree#

Problem#

Given the root of a binary tree, invert the tree, and return its root.

Examples#

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Constraints:#

Follow-up#

class Node():
    def __init__(self, val=0, left=None, right=None):
        self.val = val 
        self.left = left
        self.right = right

def levelorder_traverse(root):
    queue = [root]

    res= []
    while queue:
        node = queue.pop(0)
        res.append(node.val)

        # enqueue
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return res

# use preorder operation
def invertBinaryTree(root):

    if not root:
        return
    
    # preorder operations: swap subtrees
    root.left, root.right = root.right, root.left
    # traverse left subtree
    invertBinaryTree(root.left)
    # traverse right subtree
    invertBinaryTree(root.right)

    return root 

# test
node = Node(4)
node.left = Node(2)
node.right = Node(7)
node.left.left = Node(1)
node.left.right = Node(3)
node.right.left = Node(6)
node.right.right = Node(9)
print(levelorder_traverse(node))
node = invertBinaryTree(node)
print(levelorder_traverse(node))

[4, 2, 7, 1, 3, 6, 9]
[4, 7, 2, 9, 6, 3, 1]

# use post-order operation
def invertBinaryTree(root):
    if not root:
        return 
    
    # traverse left subtree
    left = invertBinaryTree(root.left)
    # traveres right subtree
    right = invertBinaryTree(root.right)
    # post-order operations
    root.left = right 
    root.right = left 

    return root

# test
node = Node(4)
node.left = Node(2)
node.right = Node(7)
node.left.left = Node(1)
node.left.right = Node(3)
node.right.left = Node(6)
node.right.right = Node(9)
print(levelorder_traverse(node))
node = invertBinaryTree(node)
print(levelorder_traverse(node))

[4, 2, 7, 1, 3, 6, 9]
[4, 7, 2, 9, 6, 3, 1]
Contents