BFS

广度优先算法:如果用一个树来说明就是,访问次序就是按树的层次来遍历

  • 实现:用队列来实现,

queue.push(root);


while(!queue.empty()) {

TreeNode* node = queue.pop();

queue.push(node.left);

queue.push(node.right);

}

  • 优点:可以得到最短路径、最优解
  • 缺点:如果树的层次太深、每层的节点太多、消耗的内存就太大了。

DFS

深度优先算法:如果用一个树来说明就是,从根节点按某个路径走到一个叶子节点,然后返回上一节点,走其他的路径,一直返回到根。

  • 优点:内存消耗少
  • 缺点:每次只能的到一个解、如果要得到所有的解要做记录、还要注意重复访问的问题。