[LeetCode] #102: Binary Tree Level Order Traversal

choikh0423·2022년 5월 5일


목록 보기


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).


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

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.

Additional Details:
1. deque.popleft() costs constant time.


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
            number_of_nodes_in_level -= 1
            # Adding children to nodes_to_visit queue
            if node.left:
            if node.right:
            # If nodes in one level is cleared
            if number_of_nodes_in_level == 0:
                # Re-initializing for next level
                number_of_nodes_in_level = len(nodes_to_visit)
                nodes_in_level = []
        return values_list

1. It costs too much space.

LeetCode Question #102

0개의 댓글