102. Binary Tree Level Order Traversal

Problem Statement

link: LeetCode.cn LeetCode 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).

Example:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Input: root = [1] Output: [[1]]

Input: root = [] Output: []

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

Solution Approach

The solution uses Breadth-First Search (BFS) to traverse the binary tree level by level, collecting the values of nodes at each level into separate lists.

Algorithm

1. Initialize Queue and Result List:Use a deque to manage nodes at each level and initialize an empty list res to store the results. Start by adding the root node to the queue.
2. Level-by-Level Traversal:Perform a BFS where, at each level, iterate over the current nodes in the queue. For each node, add its value to a temporary list temp and enqueue its left and right children if they exist.
3. Store Level Results:After processing all nodes at the current level, append the temp list containing that level’s node values to the res list, and continue to the next level until the queue is empty.

   Time Complexity

   O(n): Every node in the tree is visited once, where n is the number of nodes.

   Space Complexity

   O(n): In the worst case, the queue could hold all the nodes at the last level, which can be up to n/2 nodes.

Implement

    # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:
        def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
            q = collections.deque()
            res = []
            q.append(root)
            if not root:
                return []

            while q:
                temp = []
                l = len(q)
                for _ in range(l):
                    node = q.pop()
                    temp.append(node.val)
                    if node.left:
                        q.appendleft(node.left)
                    if node.right:
                        q.appendleft(node.right)
                res.append(temp)
            return res
    

    
    

Twitter  facebook  Email