Description
Invert a binary tree.
Input:
1 |
4 |
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.
Thoughts
I was not able to solve this problem at the begining. I felt myself so stupid after seeing the DFS approach for just 5 lines. After two weeks from previous submission. I was able to recall all three different approaches.
Recursive DFS (Top-down)
Recursive DFS is acutally very straight forward. For each node, swap its left & right child. Recursively call invertTree(left)
to the rest of the tree.
1 |
|
Recursive DFS (Bottom-up)
The above approach recursive dfs use top-down approach, where swap is performed along the way from top to bottom. The bottom-up approach is also possible.
1 |
// recurive dfs, bottom-up, might cause stack overflow |
The bottom-up approach first go down to the far left node in the left subtree. Then swap start from there and its right subtree and return node
to upper level. The process is very similiar to pre-order traversal.
Iterative DFS
Both recursive dfs approach might cause stack overflow if tree is extremely unbalanced, hence the height of tree might be large to cause stack overflow. Let’s take a look at the iterative approach with Stack
data structure.
1 |
// iterative dfs no stack overflow |
As we can see, iteative dfs, indeed, is very similiar to recursive top-down approach. The recursive top-down approach uses an implicit Stack
and iterative dfs uses an explicit Stack
.
Iterative BFS
Benefit from the nature of this problem, we can also use BFS to solve it.
1 |
// BFS, change stack to queue |
BFS approach uses level order traversal to push node and swap them in order. The overall strcture is very similiar to the iterative dfs version.
Summary:
- DFS recurisve (top-down)
- DFS recurisve (bottom-up, preorder traversal)
- DFS iterative (stack)
- BFS iterative (queue, level-order traversal)
Logs
- 02/03/2019 Add solutions
近期评论