BFS

思路

利用queue

模板

from collections import deque

def bfs(self, root):
    if not root:
        return []
    queue = deque()
    queue.appen(root)
    result = []
    visited = {}

    while queue:
        cur = queue.popleft()
        result.append(cur)
        for neighbour in cur.neighbours:
            if neighbour not in visited:
                queue.append(neighbour)

questions

  • Binary Tree Level Order Traversal
    • 用两个变量current level和next level的node数量
  • Binary Tree Level Order Traversal II
    • reverse
  • Binary Tree ZigZag level order Traversal
    • 根据层数reverse
  • Binary Tree Right Side View
    • 输出每层的最后一个
  • Populate next right pointer I & II(non-complete tree)
    • space O(n) 将level order traversal的code稍作改变就可以
    • space O(1)
      • I，只要保持最左边的node,然后对当前层遍历set next就可以
      • II, 因为non-complete，所以不一定是最左边开始层，要根据上面一层来set 当前层的next
  • word ladder I & II

References