💬 Discord
Sign In
NeetCode #424LC-102MediumTreesBlind 75NC 150NC 250
← Back to All Problems

#424 · #102 · Binary Tree Level Order Traversal(二叉树的层序遍历)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its level-order traversal: a list of lists, where each inner list holds the values at one depth from left to right. Constraints: the number of nodes is in [0, 2000].

💡 Core Algorithmic Approaches

  1. Breadth-first search with a queue naturally produces levels.
  2. The key detail is capturing len(queue) before processing the level, so the loop only consumes the current level's nodes.
  3. Children are appended during the level and processed in the next iteration.
  4. This is the template for all level-based tree problems.

💻 Benchmark Python3 Implementation

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        from collections import deque
        if not root:
            return []
        res = []
        q = deque([root])
        while q:
            n = len(q)                     # freeze the level size first
            level = []
            for _ in range(n):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is enqueued and dequeued once.
💾 Space Complexity
O(w) for the queue, where w is the maximum width (up to n/2 for a complete tree).

⚠️ Interview Pitfalls & Follow-ups

  • Using for node in q instead of a fixed count: the queue mutates during iteration and the levels would merge.
  • Forgetting to freeze len(q): the same problem, since children are appended mid-level.
  • Appending None children: they would break the level grouping; the if node.left guards are needed.
  • Returning a flat list: the answer must be grouped by level.