102. Binary Tree Level Order Traversal

Problem

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],

Example:

3 / \ 9 20 / \ 15 7

return its level order traversal as:

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

Thought Process

White Board

Below is the white board:

Code

class ListQueue:
    # implement Queue based on List
    def __init__(self):
        self.array = []
        self.head = 0
        self.tail = 0

    def __len__(self):
        return self.tail - self.head

    def push(self, value):
        self.array[self.tail] = value
        self.tail += 1

    def pop(self):
        value = self.array[self.head]
        self.head += 1
        return value

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root):
        res = []

        if root is None:
        # if the tree is empty
            return res

        lq = ListQueue()
        # initialize list queue

        lq.push((root, 0))
        # (the node, the level)

        while lq is not None:
            curr_node = lq.head[0]
            level = lq.head[1]
            lq.pop()

            if level == len(res):
                res.append([])

            res[level].append(curr_node.value)

            if curr_node.left:
                lq.push((curr_node.left, level + 1))

            if curr_node.right:
                lq.push((curr_node.right, level + 1))

        return res


Complexity

  • Time complexity is O(n*m)
  • used additional ds to creat stack

Optimization

Will try to figure out a recursive solution in the future.