BST - Level Order Traversal

BFS + Priority Queue

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

from collections import deque

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        else:
            que = deque([(root, 0)])
            # memo only stores values of nodes
            memo = []
            while que:      
                node, level = que.popleft()
                if node:
                    # 因為需指定level(list中的位置)插入, 故需要此判斷式
                    # e.g. memo now is [] and after first pop, level is 0
                    # len(memo) = 0 level = 0
                    if len(memo) < level + 1:
                        memo.append([])
                    memo[level].append(node.val)
                    que.append((node.left, level + 1))
                    que.append((node.right, level + 1))
            return memo