Leetcode Invert Binary Tree

Tags: , ,

Invert a binary tree.

to

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 fuck off.

Analysis

This problem can be solved by using both recursion and bread first traverse or Level order traverse. 

We first invert the left tree and right tree, then put the inverted right tree as the left child, and the inverted left tree as right child.

See the following recursive algorithm in Java.

Java Solution

Java Solution – Level order traverse

In the process of level order traverse of the tree, we swap the left child and right child, then we put the new left child before the new right child in the queue. We keep doing this until all the children are visited.