如何实现BFS和DFS搜索算法？

BFS(广度优先搜索)和DFS(深度优先搜索)是两种重要的搜索算法。我们可以在二叉树中实现BFS和DFS搜索算法如下:

BFS:

public List<Integer> BFS(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        result.add(curr.val);
        if (curr.left != null) queue.offer(curr.left);
        if (curr.right != null) queue.offer(curr.right);
    }

    return result;
}

DFS:

public List<Integer> DFS(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        result.add(curr.val);
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }

    return result;
}

BFS使用队列实现,DFS使用栈实现。算法流程大致相同,主要区别在于:
BFS:每层节点从左到右依次入队出队,宽度优先。
DFS:深度优先,先入栈的节点先访问。

所以,BFS和DFS算法的关键是:

1. BFS使用队列,DFS使用栈。
2. 遍历根节点,将左右子节点加入队列或栈。
3. 从队列或栈中取出节点curr,访问curr,将其左右子节点加入队列或栈。
4. 重复步骤3,直到队列或栈为空,得到结果。
5. 与递归方法相比,只是使用队列/栈代替了递归调用栈。

时间复杂度O(n),空间复杂度O(n)。