Subject to introduce

Force buckle 102: leetcode-cn.com/problems/bi…

Analysis of the

This article will explain why this problem is suitable for breadth-first search (BFS) and what scenarios BFS is suitable for.

DFS (depth-first search) and BFS (breadth-first search) are like twins, one always comes to mind with the other. In practice, however, we use DFS far more than BFS. So is BFS useless?

If we use DFS/BFS just to traverse all the nodes of a tree or graph, then DFS and BFS are no different in power, and we prefer DFS traversal that is easier to write and less complex in space. However, there are certain usage scenarios that DFS cannot do and you can only traverse using BFS. These are the two scenarios covered in this article: “sequence traversal” and “shortest path”.

DFS and BFS

Let’s first look at the code comparison between DFS traversal and BFS traversal on a binary tree.

DFS traversal uses recursion:

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

BFS traversal uses queue data structures:

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while(! queue.isEmpty()) { TreeNode node = queue.poll();// Java pop write poll()
        if(node.left ! =null) {
            queue.add(node.left);
        }
        if(node.right ! =null) { queue.add(node.right); }}}Copy the code

Just comparing two pieces of code, the most intuitive feeling is: DFS traversal code is much simpler than BFS! This is because the recursive approach implicitly uses the stack of the system and we do not need to maintain a data structure ourselves. If you simply walk through the binary tree, then DFS is obviously the more convenient choice.

Although DFS and BFS traverse all nodes of binary tree once, they traverse nodes in different order.

This traversal order is also the fundamental reason why BFS can be used to solve “sequence traversal” and “shortest path” problems.

What is sequential traversal? Simply put, sequential traversal means layering a binary tree and traversing each layer from left to right:

At first glance, this traversal order is the same as BFS, we can directly use BFS to obtain the sequence traversal results. However, sequence traversal requires different input results than BFS. Sequential traversal requires us to differentiate each layer, which returns a two-dimensional array. The BFS traversal results in a one-dimensional array that does not distinguish between each layer.

So, how do you layer the results of BFS traversal? Let’s first observe the process of node entering and leaving the queue during BFS traversal, capturing a certain moment in the BFS traversal process:

As you can see, the nodes in the queue are 3, 4, and 5 from layer 1 and layer 2 respectively. At this point, the nodes of tier 1 come in before the nodes of tier 2 go out, and the nodes of tier 2 are next to each other in the queue, so we can’t tell which tier the nodes in the queue come from.

Therefore, we need to modify the code slightly to record the number of nodes in the queue nn (i.e. the number of nodes in this layer) before each layer is traversed, and then process the nn nodes in this layer in one go.

// Order traversal of binary tree
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while(! queue.isEmpty()) {int n = queue.size();
        for (int i = 0; i < n; i++) { 
            // The variable I has no real meaning, just to loop n times
            TreeNode node = queue.poll();
            if(node.left ! =null) {
                queue.add(node.left);
            }
            if(node.right ! =null) { queue.add(node.right); }}}}Copy the code

In this way, we transform BFS traversal into sequential traversal. In the traversal process, the process of node entering and leaving the queue is as follows:

As you can see, in each round of the while loop, all nodes of the current layer are dequeued, and all nodes of the next layer are queued, thus realizing the sequence traversal.

Finally, the solution code is as follows:

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Queue<TreeNode> queue = new ArrayDeque<>();
    if(root ! =null) {
        queue.add(root);
    }
    while(! queue.isEmpty()) {int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if(node.left ! =null) {
                queue.add(node.left);
            }
            if(node.right ! =null) {
                queue.add(node.right);
            }
        }
        res.add(level);
    }

    return res;
}
Copy the code