Tree Traversal BFS

Catalogue

1. 1. 102. Binary Tree Level Order Traversal
2. 2. 107. Binary Tree Level Order Traversal II
3. 3. 637. Average of Levels in Binary Tree
4. 4. 103. Binary Tree Zigzag Level Order Traversal
5. 5. 662. Maximum Width of Binary Tree

Linked List Queue

1. 1. 116. Populating Next Right Pointers in Each Node
2. 2. 117. Populating Next Right Pointers in Each Node II

BFS Level Order Traversal

• When should we change layer to the next?

1. use a new Queue to record next level!
2. use a value to record the size of the queue on the current level

102. Binary Tree Level Order Traversal

• use two 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

107. Binary Tree Level Order Traversal II

• just reverse the results of 102?

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

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

• Another Solution : Use Deque!
  In the even level:expand a node from the right end of the dequ, generate right and then left child, and insert them to the left end of the deque.

662. Maximum Width of Binary Tree

if use index to calculate whicn index in its level

• 2 idx, 2 idx + 1

class Solution(object):
    def widthOfBinaryTree(self, root):
        if not root:
            return 0

        queue = [(root, 0)]
        res = 1
        while queue:
            nqueue = []
            for node, idx in queue:
                if node.left:
                    nqueue.append((node.left, 2*idx))
                if node.right:
                    nqueue.append((node.right, 2*idx+1))
            if nqueue:
                res = max(res, nqueue[-1][1] - nqueue[0][1] + 1)
            queue = nqueue
        return res

Linked List Queue

• O(1) Space complexity

116. Populating Next Right Pointers in Each Node

• Actually its the “linked list” version BFS, so space complexity is constant!!

  class Solution:
      def connect(self, root):
          if not root:
              return
  
          cur = root
          while cur.left:
              head = cur.left
              while cur:
                  cur.left.next = cur.right
                  if cur.next:
                      cur.right.next = cur.next.left
                  cur = cur.next
              cur = head

117. Populating Next Right Pointers in Each Node II

• Do not know the head of next level, so DummyNode make it easier to implement!!!

  class Solution:
      def connect(self, root):
          if not root:
              return
          
          DummyNode = TreeLinkNode(-1)
          head = root
          while head:
              DummyNode.next = None
              prev = DummyNode
              cur = head
              while cur:
                  if cur.left:
                      prev.next = cur.left
                      prev = cur.left
                  if cur.right:
                      prev.next = cur.right
                      prev = cur.right
                  cur = cur.next
              head = DummyNode.next