遍历算法DFS与BFS

DFS（深度优先搜索）和 BFS（广度优先搜索）就像孪生兄弟，提到一个总是想起另一个。然而在实际使用中，我们用 DFS 的时候远远多于 BFS。那么，是不是 BFS 就没有什么用呢？

如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。

DFS 与 BFS

让我们先看看在二叉树上进行 DFS 遍历和 BFS 遍历的代码比较。

DFS 遍历使用递归：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

从代码可以看出递归调用实际上是 维护了一个栈的存在最初的时候是不停的压栈，最后会出栈。
BFS 遍历使用队列数据结构：

public void BFS(TreeNode treeNode) {
        //深度优先遍历使用队列来记录
        //1首先构造队列数据结构
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(treeNode);
        //将head加入到队列后中遍历孩子
        while (queue.size() != 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }

        }
    }

由于广度遍历是水波纹的样子向外延伸而不是通过根节点来遍历左右孩子，所以使用队列来进行遍历。