1. Breadth First Search (BFS)

Definition: Also known as hierarchy traversal, from top to bottom for each layer, from left to right (can also be from right to left) to visit the nodes, after visiting a layer to enter the next layer, until there are no nodes.

Just to visualize it:

Let’s talk about how to solve the problem:

Breadth-first traversal is a layer-by-layer traversal. We can use a queue (first-in, first-out) to store the nodes of each layer. When traversing each node, we take the nodes of the next layer and put them at the end of the queue. When we put the nodes in, we record the number of nodes in the layer, so that we can distinguish the nodes of each layer in the queue, thus completing the breadth-first traversal.

Let’s look at the code template for breadth-first traversal

And then let’s do an example

Then I use breadth-first traversal to solve the problem. I write each line of comment in the code, and then look at the code:

/** * width first traversal *@paramRoot Root node *@returnThe result set * /
public List<List<Integer>> levelOrder(TreeNode root) {
    // To store the result set
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    if (root == null) {
        return ret;
    }

    // queue, used to enter and exit nodes
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    // Put the root node in the queue first
    queue.offer(root);
    while(! queue.isEmpty()) {//level is used to store node data of each layer
        List<Integer> level = new ArrayList<Integer>();
        // The number of nodes in the current layer
        int currentLevelSize = queue.size();
        // Traverses the nodes of the current layer
        for (int i = 1; i <= currentLevelSize; ++i) {
            Poll a node from the queue
            TreeNode node = queue.poll();
            // Add node data to the layer collection
            level.add(node.val);
            // If the current node has a node of the next tier, put the node of the next tier to the end of the queue
            if(node.left ! =null) {
                queue.offer(node.left);
            }
            if(node.right ! =null) { queue.offer(node.right); }}// Iterate over the layer node and add to the result set
        ret.add(level);
    }
    // Return the result set
    return ret;
}
Copy the code

I think there are two main points to solve the breadth-first search problem: one is to use a queue to enter and exit nodes; The second is to take the number of nodes of the current layer, through this number to get nodes in the queue, that is, nodes in the first layer.

2. Depth-first Search (DFS)

Depth-first search is a search for every possible branch path, and each node can only be accessed once.

Just to visualize it:

Let’s get straight to an example:

Here we use backtracking recursion to solve the problem, looking directly at the code:

// Define the result set
List<List<Integer>> ret = new LinkedList<List<Integer>>();
// Use a stack to store paths
Stack<Integer> path = new Stack<>();
/** * depth-first traversal *@paramRoot and node *@paramThe sum target and */
public void dfs(TreeNode root, int sum) {
    if (root == null) {
        return;
    }
    // Push the root node onto the stack first
    path.push(root.val);
    // The target value minus val of the node
    sum -= root.val;
    // The node has no children and the destination sum is 0, indicating that such a path is satisfied
    if (root.left == null && root.right == null && sum == 0) {
        // Add the result set
        ret.add(new LinkedList<Integer>(path));
    }
    // Iterate over the left node
    dfs(root.left, sum);
    // iterate over the node
    dfs(root.right, sum);
    // Eject the current node (traceback)
    path.pop();
}
Copy the code

Is there a recursion that looks a lot like a binary tree’s first order, middle order, and subsequent traversal? In fact, the first order, middle order and subsequent traversal of binary tree is also a depth-first traversal algorithm, so it seems to have the same meaning here.

And it’s very similar to the backtracking algorithm that we did before. If you’re interested, you can read my previous article.

Ok, know the binary tree before the order traversal is also a kind of depth-first traversal, I believe many readers know the binary tree before the order traversal non-recursive writing, using the stack as the middle storage data structure, here also put the binary tree before, after the order traversal code pasted here.

3. Front, middle, and back traversal of binary trees

// Traversal: root -> left -> right
public void firstTraversal(Node root){
  			// Define a stack
        Stack<Node> stack = new Stack<>(); 
  			// Check whether the node is empty or whether the stack is empty. If both are empty, end the loop
        while(root! =null||stack.size()>0) {if(root! =null){
                printNode(root);
                stack.push(root);
                root = root.getLeftNode();
            }else{ root = stack.pop(); root = root.getRightNode(); }}}Copy the code
// Order traversal: left -> root -> right
    public void inOrderTraversal(Node root){
        Stack<Node> stack = new Stack<>(); // Define a stack
        while(root! =null||stack.size()>0) {if(root! =null){
                stack.push(root);   // push directly into the stack
                root = root.getLeftNode();
            }else {
                root = stack.pop(); // Output when out of the stackprintNode(root); root = root.getRightNode(); }}}Copy the code
// Continue traversal: left -> right -> root
public void postOrderTraversal(Node root){
        Stack<Node> stack = new Stack<>();
        Stack<Node> output = new Stack<>();// Construct an intermediate stack to store the result of the sequential traversal
        while(root! =null||stack.size()>0) {if(root! =null){
                output.push(root);
                stack.push(root);
                root = root.getRightNode();
            }else{ root = stack.pop(); root = root.getLeftNode(); }}while (output.size()>0){ printNode(output.pop()); }}Copy the code

conclusion

1. Breadth-first traversal: traversal layer by layer, using a queue as the intermediate storage, taking the number of nodes of the current layer, traversal the nodes of the current layer, and recording the nodes of the next layer to complete breadth-first traversal;

2. Depth-first traversal: The code in this paper uses the backtracking method, first writing the recursive termination condition and the processing of the result set, then traversing the left and right subtree nodes, and then pop() the current node. It is worth noting that the front, middle, and back traversals of binary trees are also depth-first traversals.

Can see here are talents, your likes collection is my biggest power ~ also welcome to follow the public account “mountain master”, unlock more dry goods ~