102. Binary Tree Level Order Traversal

Description:

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

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
[1] using queue)

code::
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # exception handle
        if not root:
            return []
        
        # init
        level_order=[]
        queue=deque()
        queue.append(root)
        
        while queue:
            size=len(queue)
            
            tmp=[]
            for i in range(size):
                cur=queue.popleft()
                tmp.append(cur.val)
                
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            level_order.append(tmp[:])
        return level_order
        
-T/C: O(n)
-S/C: O(2^h)==O(2^(logn))==O(n) # worst case
'''

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # exception handle
        if not root:
            return []
        
        # init
        level_order=[]
        queue=deque()
        queue.append(root)
        
        while queue:
            size=len(queue)
            
            tmp=[]
            for i in range(size):
                cur=queue.popleft()
                tmp.append(cur.val)
                
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            level_order.append(tmp[:])
        return level_order