102. Binary Tree Level Order Traversal

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
 9        if not root:
10            return []
11
12        dq = deque([(root, 0)])  # node, level
13        last_level = 0
14        result = []
15        level_result = []
16
17        while dq:
18            node, level = dq.popleft()
19            if level > last_level:
20                last_level = level
21                result.append(level_result)
22                level_result = []
23            level_result.append(node.val)
24            if node.left:
25                dq.append((node.left, level + 1))
26            if node.right:
27                dq.append((node.right, level + 1))
28
29        result.append(level_result)
30
31        return result

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
 9        if not root:
10            return []
11
12        dq = deque([root])
13        result = []
14
15        while dq:
16            level_result = []
17            for _ in range(len(dq)):
18                node = dq.popleft()
19                level_result.append(node.val)
20                if node.left:
21                    dq.append(node.left)
22                if node.right:
23                    dq.append(node.right)
24            result.append(level_result)
25
26        return result