Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ , [9,20], [15,7] ]
- This is a typical BFS problem
- Can solve it with the help of a queue
- In Python, can use collection.deque for queue
# Definition for a binary tree node. from collections import deque class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def levelOrder(self, root): # initialization res = [] # a list of list q = deque() level = 0 # store the level info curr = (root, level) q.append(curr) #append both node and its level # if the tree is empty if root is None: return  # loop as long as q has element while q: curr = q.popleft() node, level = curr, curr if level == len(res): # level should be 1 less than the length of result # if level equals the len of result, need to start a new array for new level res.append() res[level].append(node.val) if node.left: q.append((node.left, level+1)) if node.right: q.append((node.right, level+1)) return res
- Time complexity is O(n), a while loop is used
- Space complexity is also O(n), a deque is used to store node and its level info
Below is the white board:
How to improve?