# [LeetCode] #102: Binary Tree Level Order Traversal

choikh0423·2022년 5월 5일
0

## LeetCode

목록 보기
8/11 ## Problem:

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

## Process:

Objective: Returning the values of nodes in the order of level order traversal.

Constraints:
1. The number of nodes in the tree is in the range [0, 2000].
2. -1000 <= Node.val <= 1000

Edge Cases:
1. The tree is empty.
2. The tree is incomplete.

1. deque.popleft() costs constant time.

## Solution:

### Attempt #1: Counting the number of nodes in each level

• Time Complexity: O(n), where n is the number of nodes
• Space Complexity: O(n), more specifically O(3n)

How it works:
During each level:
1. Append the node value to nodes_in_level list
2. Subtract 1 from the number_of_nodes_in_level to keep track of how many nodes of that specific level are left.
3. Add child nodes into the nodes_to_visit queue.

When you are done with the nodes in one level:
1. Append the nodes_in_level list to the values_list to store the values of that level into the final list that will be returned.
2. Refresh the nodes_in_level list to be empty and number_of_nodes_in_level to be 0.

from collections import deque

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
values_list = []
number_of_nodes_in_level = 1
nodes_in_level = []
nodes_to_visit = deque([root])

# If the tree is empty
if not root:
return []

while nodes_to_visit:
node = nodes_to_visit.popleft()

# Adding the node value to nodes_in_level
nodes_in_level.append(node.val)
number_of_nodes_in_level -= 1

# Adding children to nodes_to_visit queue
if node.left:
nodes_to_visit.append(node.left)
if node.right:
nodes_to_visit.append(node.right)

# If nodes in one level is cleared
if number_of_nodes_in_level == 0:
values_list.append(nodes_in_level)

# Re-initializing for next level
number_of_nodes_in_level = len(nodes_to_visit)
nodes_in_level = []

return values_list

Limitations:
1. It costs too much space.

LeetCode Question #102