题目

总结

1. 如果有两类点， A, B.
   1. 既可以通过A找B
   2. 也可以通过B找A
   3. 要看哪一种方式省时间复杂度
2. 出奇的是, 二叉树上的层序遍历既能够用bfs, 也能够用dfs, 而且dfs更快, 更容易控制每层的顺序, 倒序.
   1. 例子
      1. Binary Tree Level Order Traversal
      2. Binary Tree Level Order Traversal II
      3. Binary Tree Zigzag Level Order Traversal
      4. Convert Binary Tree to Linked Lists by Depth
3. bfs 循环里面根据题目的条件作判断, 最好是对current node 作判断. 避免只有一个node的情况
4. 如果题目设计每一层深度或者高度，可以考虑用bfs，如 Nested List Weight Sum II
5. 拓扑排序
   1. 有向无环图
   2. 什么时候用?
      1. 当一对一对的Sequence像[1, 2]出现, 并且他们需要按照一定的顺序组合成一个大的Sequence, 某些元素必须要在某些前面
   3. 步骤
      1. get a table of Indegrees
      2. put all node with zero indegree to queue
      3. while queue is not empty
         1. loop through the neighbors of curt node
            1. adj's indegree decrement, update map
            2. if adj's indegree == 0, enqueue
6. 矩阵
   1. 如果题目涉及 "到达所有的XXX, 则返回结果, 否则返回-1" 那么, 在进行bfs前必须统计出XXX的个数
   2. 题目如
      1. Zombie in Matrix
      2. Build Post office II
7. 什么时候dfs 会比bfs快?
   1. 没有多余的工作. 不是找最短路径, 而是traverse这个图. 比如二叉树和简单图的dfs会比bfs快.
   2. 否则, 因为dfs有太多分支, 即使dfs已经找到了最优解, 但是其他分支还是会继续执行直到碰壁.