Recently, I have been writing questions about trees. In fact, trees are also the questions that interviewers like to investigate in the interview. Those of you who know a little bit about trees know that solving these kinds of problems is either traversal, BFS (breadth first) or DFS (depth first). Both of these are actually easy to understand, as the name suggests, search from that side first, traverse in turn. Today we are going to talk about BFS, DFS for next time.

The structure of a tree looks something like this:

The core of the breadth-first algorithm is to traverse a tree hierarchically. For this tree, the order of traverse is 12->7->1->9->10->5. So how do you traverse the tree in this order? The nodes in the same hierarchy don’t seem to be related. And then later we have to figure out how to get them to do that.

Let’s start with a problem: given a binary tree, fill an array to represent its hierarchy. Fill each level left to right into a separate subarray and return the last array.

When I get it, I find that the problem expresses hierarchy very directly to us, using breadth first. And we don’t need to do anything extra, just walk through it.

We first have to solve the problem of getting nodes at the same level to process in order. We can find that the order of nodes at the same level is determined by nodes at the previous level, so we can already know the order of children at the next level when we process nodes at the previous level. That you only need to use a data structure to traverse to the child node save in accordance with the order, we can use the Queue this data structure (in fact, other data structures can also, just suit to save some Queue processing finished and put things in sequence, and the data quantity is changing all the time, there will be frequent in the remove operation, So more convenient than List or Queue). A Queue makes it easy to do breadth-first searches of trees. We will probably have the following steps:

  1. Add the root node to the Queue.
  2. As long as there are elements in this Queue, it keeps iterating.
  3. For each iteration, we first count how many elements are in the current Queue, and that’s the number of elements at the current level of the tree, which we’ll call levelSize.
  4. Next, remove the levelSize elements from the Queue and do something to them that fits our problem.
  5. As each node is removed, its children are added to the Queue.
  6. As long as there are elements in the Queue indicating a next level, repeat step 3 for the next level.

That’s it. Doesn’t it seem easy? But often is this simple search, a lot of people just can’t come out.

According to the steps analyzed above, we will implement the following algorithm:

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(! queue.isEmpty()) {int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);
                // Insert the child node into the queue
                if(currentNode.left ! =null)
                    queue.offer(currentNode.left);
                if(currentNode.right ! =null)
                    queue.offer(currentNode.right);
            }
            result.add(currentLevel);
        }

        return result;
    }
Copy the code

Just get the current level beforehand to control the loop and add the child nodes to the queue, and then the process is complete, and you can do whatever you want with each child element or level. It’s pretty easy to do it in reverse order, in an S shape.

From the above discussion, we must have a perceptual understanding of BFS. Next, let’s look at a variation to further enhance the impression of breadth-first search.

It works like this: Given a binary tree, connect a node at each level to its next node at that level, with the last node of each level pointing to NULL.

This is the same problem as the one above, so let’s follow the same pattern to solve the problem. Again, we use the breadth-first algorithm, the only difference is, as we traverse a hierarchy, we have to remember the previous node, so that it connects to the next node. The rest of the process is the same as before.

public static void connect(TreeNode root) {
        if (root == null)
            return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(! queue.isEmpty()) { TreeNode previousNode =null;
            int levelSize = queue.size();
            // Connect the current layer to all the points
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if(previousNode ! =null)
                    previousNode.next = currentNode;
                previousNode = currentNode;

                // Insert the children of the current node into the queue
                if(currentNode.left ! =null)
                    queue.offer(currentNode.left);
                if(currentNode.right ! =null) queue.offer(currentNode.right); }}}Copy the code

Look, all changes are in its ancestor, change the soup is the same, as long as we master the basic problem solving steps, and then encountered these deformation problems, as long as the beginning of the intent of the topic, always in accordance with our ideas step by step to write out the algorithm. And the so-called breadth-first algorithm, in the current view is also so things, general general.

Ok, that’s all for BFS today. You can also brush some types of topics to summarize your own rules and routines and form your own awareness of the topic. New topics are put forward online every day, and only by mastering the core can you maximize your efficiency. Happy coding~