Binary tree level order traversal#

Levels: level-3

Data structures: tree

Algorithms: bfs

Practice Link#

Description#

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example#

 1Given binary tree [3,9,20,null,null,15,7],
 2
 3    3
 4   / \
 5  9  20
 6    /  \
 7   15   7
 8
 9Output:
10[
11  [3],
12  [9,20],
13  [15,7]
14]

Python Solution#

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution(object):
 9    def levelOrder(self, root):
10        """
11        :type root: TreeNode
12        :rtype: List[List[int]]
13        """
14        if not root:
15            return []
16        ans, level = [], [root]
17        while level:
18            ans.append([node.val for node in level])
19            temp = []
20            for node in level:
21                temp.extend([node.left, node.right])
22            level = [leaf for leaf in temp if leaf]
23        return ans