[LeetCode/릿코드] 102. Binary Tree Level Order Traversal

Clarify the problem

Problem: Return the level-order traversal of a binary tree's node values from left to right and level by level
Input: The root node of a binary tree
Output: A list of lists containing the values of the the binary tree by level

Example:

  1
 / \
2   3
   / \
  4   5
-> [[1],[2,3],[4,5]]

Design a solution

Idea

We can traverse the binary tree level by level using Breadth-First Search (BFS) with a queue. The key idea is to use the queue to maintain the correct order of nodes and to use the number of elements in the queue to separate each level.

Algorithm

1. Intialize an empty result list to store the value of each level and a queue by implementing the input root node as a seed
2. Add an early exit: if an input root is None, return the empty result list
3. Set BFS

• Set a while loop, while the queue is not empty
• Get the current size of the queue (this represents the numbner of nodes at the current level)
• Intialize a temporary list for each level
• For loop count times:
  - Pop the node from the queue
  - Append the value of node to the temporary list
  - If the left child exist, add it to the queue
  - If the right child exist, add it to the queue
• Append the temporary list to the result list

4. Return the result list

Implement the code

from collections import deque
class Solution:
    def levelOrder(self, root):
        
        # Initialize
        res = []
        if not root:            # early guard
            return res      
        queue = deque([root])     # implement the seed

        # Run BFS 
        while queue: 
            n = len(queue)
            temp = []
            # for loop for each level
            for _ in range(n):
                # base
                node = queue.popleft()
                temp.append(node.val)

                # propagate
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            res.append(temp)

        # Return the result
        return res

Self Review (Eye Test)

working

Time and Space Complexity

Time complexity: O(n), where n is the number of nodes in the binary tree, since each node is visited exactly once.
Space compleixty: O(n), because in the worst case, the queue can store up to n/2 nodes and the result list can store up to n nodes

Polish the Solution