[LeetCode] 226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

1 2 3 4 5

4 / \ 2 7 / \ / \ 1 3 6 9

Output:

1 2 3 4 5

4 / \ 7 2 / \ / \ 9 6 3 1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Solution

1
2
3
4
5

data Tree a = Node a (Tree a) (Tree a) | EmptyNode

invert :: Tree a -> Tree a
invert EmptyNode = EmptyNode
invert (Node val left right) = Node val (invert right) (invert left)

3 simple steps to solve this:

1. Get an opportunity to be interviewed onsite at Google (99% completed)
2. Swap the left subtree and right subtree (99.5% completed)
3. Call invert on their subtrees (100% completed)

Excellent! Now you are qualified for an engineer position at Google! (XD

Don’t worry if you stuck on step 2 and 3, you can still get hired by Apple!