102_Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

Level: medium

Tag: tree, breadth-first search, deepth-first search

Question

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

Example 1

Input: 
    3
   / \
  9  20
    /  \
   15   7

Output: 
[
  [3],
  [9,20],
  [15,7]
]

Idea 1 (breadth-first search)

• For each level, find all the node value, append to the result as a list.

• Have a temporary list to store all the left and right child for all the node in the level.

Solution 1: breadth-first search

Time: $O(n)$

Space: $O(n)$

# 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):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        res = []
        if root == None:
            return res

        level = [root]
        while len(level) > 0:
            # For each level, find all the node value, append to the result as a list
            res.append([node.val for node in level])
            # a temporary list to store all the left and right child for all the node in the level
            temp = []
            # append left and right child if they are not None
            for node in level:
                if node.left != None:
                    temp.append(node.left)
                if node.right != None:
                    temp.append(node.right)
            level = temp

        return res

Solution 2: deepth-first search (harder to understand)

Time: $O(n)$

Space: $O(n)$

# 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):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        res = []
        self.dfs(root, 0, res)
        return res

    def dfs(self, root, depth, res):
        if root == None:
            return res
        if len(res) < depth+1:
            res.append([])
        res[depth].append(root.val)
        self.dfs(root.left, depth+1, res)
        self.dfs(root.right, depth+1, res)