102. Binary Tree Level Order Traversal

[sophryu99]

102. Binary Tree Level Order Traversal

1. Append the root to the deque
2. For the current level, iterate through all node and pop the root node

from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root: return []
        queue, res = deque([root]), []
        # Append the root to the deque
        while queue:
            # For the current level, iterate through all node and pop the root node
            cur_level, size = [], len(queue)
            for _ in range(size):
                node = queue.popleft()
                # If there is left chid, append to the queue
                if node.left:
                    queue.append(node.left)
                # If there is right chid, append to the queue
                if node.right:
                    queue.append(node.right)
                # Append the current root node's val to the current level array
                cur_level.append(node.val)
            # Append the current level's val to the res
            res.append(cur_level)
        return res

n: number of node

• Time Complexity: O(n) visiting every node once
• Space Complexity: O(n) size of the q