LeetCode-in-All

226. Invert Binary Tree

Easy

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

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]

Example 3:

Input: root = []

Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution

; Definition for a binary tree node.
#|
; val : integer?
; left : (or/c tree-node? #f)
; right : (or/c tree-node? #f)
(struct tree-node
  (val left right) #:mutable #:transparent)

; Helper function to create a tree node.
|#
(define (make-tree-node val [left #f] [right #f])
  (tree-node val left right))

; Function to invert a binary tree.
(define/contract (invert-tree root)
  (-> (or/c tree-node? #f) (or/c tree-node? #f))
  (cond
    [(not root) #f] ; Base case: empty tree.
    [else
     (make-tree-node
      (tree-node-val root)
      (invert-tree (tree-node-right root))
      (invert-tree (tree-node-left root)))]))

This site is open source. Improve this page.