Return the level order traversal of a binary tree. Pretty straightfoward, just conduct BFS.
The solution is as follows:
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans = []
queue = [root]
while queue:
curr_queue, queue = queue, []
level = []
for node in curr_queue:
if node:
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(level)
return ans_ Time Complexity:
O(n) - We traverse O(n) nodes of the tree.
_ Space Complexity:
O(n) - The queue can contain at most O(n) nodes of the tree.