By Long Luo

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

# BFS

Use BFS to level traversal, a List to store the Nodes of each level.

In fact, we just need a Node to store the Previous Node.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# BFS + LinkedList

Each level can be seem as a Linked List.

For example, the root node is a linked list with one node, and the second level is a linked list with two nodes and so on…

In fact, we just need a Node to store the $Previous Node$.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

# Recursion

It’s a little difficult but easy to get it.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗