BFS Level Order Traversal

102. Binary Tree Level Order Traversal

• 解法1. Two queues

用一个Queue保存下一层要遍历的节点

class Solution(object):
    def levelOrder(self, root):
        if not root: return []

        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            nqueue = []
            for node in queue:
                if node.left: 
                    nqueue.append(node.left)
                if node.right: 
                    nqueue.append(node.right)
            queue = nqueue
        return res

• 解法2. One Queue

Key Point: when should we change layer to the next?

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []

        queue = collections.deque([root])
        res = []
        while queue:
            l = len(queue) # save the size of queue
            level = []
            for _ in xrange(l):
                node = queue.popleft()
                level.append(node.val)
                if node.left: 
                    queue.append(node.left)
                if node.right: 
                    queue.append(node.right)
            res.append(level)
        return res

107. Binary Tree Level Order Traversal II

正着BFS的结果倒过来而已！

class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            nqueue = []
            for node in queue:
                if node.left: 
                    nqueue.append(node.left)
                if node.right: 
                    nqueue.append(node.right)
            queue = nqueue
        return res[::-1]

637. Average of Levels in Binary Tree

class Solution(object):
    def averageOfLevels(self, root):
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            level = [node.val for node in queue]
            ret = 1.0 * sum(level) / len(level) 
            res.append(ret)
            nqueue = []
            for node in queue:
                if node.left:
                    nqueue.append(node.left)
                if node.right:
                    nqueue.append(node.right)
            queue = nqueue
        return res

103. Binary Tree Zigzag Level Order Traversal

Deque

• Case1: if we are on the odd level: do the same as BFS1, expand a node from the left end of the deque, generate left and then right child, and insert them to the right end of the deque.
• Case2: if we are on the even level: expand a node from the right end of the deque, generate right and then left child, and insert them to the left end of the duque.

class Solution(object):
    def zigzagLevelOrder(self, root):
        if not root:
            return []

        queue = [root]
        res = []
        while queue:
            level = [node.val for node in queue]
            if len(res) % 2:
                level.reverse()
            res.append(level)
            nqueue = []
            for node in queue:
                if node.left: nqueue.append(node.left)
                if node.right: nqueue.append(node.right)
            queue = nqueue
        return res