Binary Tree Level Order Traversal
Question
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:
[
[3],
[9,20],
[15,7]
]
Tags
- Tree
- BFS
Thought
Use BFS search for all the nodes. In order to confirm the level of each node, we can add the level with the node together in the queue for BFS.
Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
Use BFS search
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
if root is None:
return result
queue = [(0, root)]
while queue:
level, ptr = queue.pop(0)
if ptr.left is not None:
queue.append((level + 1, ptr.left))
if ptr.right is not None:
queue.append((level + 1, ptr.right))
if len(result) == level:
result.append([ptr.val])
else:
result[level] += [ptr.val]
return result