102. Binary Tree Level Order Traversal
Medium LeetCodeGiven the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2
Input: root = [1]
Output: [[1]]
Example 3
Input: root = []
Output: []
Constraints
- The number of nodes in the tree is in the range [0, 2000]
- -1000 <= Node.val <= 1000
How to solve the problem
Code
- BFS(Two Array)
Python
# 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
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# BFS with two array
if root is None:
return []
ans = []
cur = [root]
while cur:
nxt = []
vals = []
for node in cur:
vals.append(node.val)
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
cur = nxt
ans.append(vals)
return ans
- BFS(Queue)
Python
# 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
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# BFS with queue
if root is None:
return []
ans = []
q = deque([root])
while q:
vals = []
for _ in range(len(q)):
node = q.popleft()
vals.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(vals)
return ans
- BFS(Queue) Written by myself
Python
# 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
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# BFS with queue
if root is None:
return []
result = []
queue = deque([root]) # deque's object must be iterable
while queue: # When queue is not empty, do the while loop
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val) # node structure: node = TreeNode(val=3, left=..., right=...)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!