This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Yes, this is the previous post “Ok, BFS, Again!” “, which aims to pick up basic data structures learned and forgotten through a brief review;

DFS, full name is: Depth_First_Search, usually compared with BFS Breadth first search (embosses-first search) understanding learning;

Remember, in the last summary of the previous chapter:

BFS is a search algorithm using queues. (DFS, as opposed, is stacked.)

That’s right! Strengthen understanding again:

  • DFS adopts the form of stack, that is, first in, last out;
  • BFS takes the form of a queue, that is, first-in, first-out;

Depth-first does not need to remember all nodes, so it occupies a small space, while breadth first requires that all nodes occupy a large space.

As an aside: More space is needed, less time is needed; Less space takes up more time, time for space, or space for time; Can be associated with, in functional programming and non-functional programming also have this idea, FP language memory, lazy evaluation, time, faster calculation, more reasonable; Non-fp language, small memory, variable frequently modified, small memory, but more time consumption;

OK, a picture is worth a thousand words:

It can be seen that DFS depth-first traversal is not layer by layer like BFS breadth-first traversal, but longitudinal traversal of all the child nodes in the situation of “go to black on one road” and “don’t hit the south wall and don’t turn back”, and then return to the sibling node, traversal the child nodes of the sibling node again, and directly complete the traversal.

The small example still needs to traverse the DOM tree, using DFS solution:

function deepFirstSearch(node) { var nodes = []; if (node ! = null) { var stack = []; / / stack! stack.push(node); While (stack.length! = 0) { var item = stack.pop(); // Remove the last element from the stack nodes.push(item); Var children = item.children; for (var i = children.length - 1; i >= 0; i--) stack.push(children[i]); }} return nodes; } deepFirstSearch(document.getElementsByTagName("body")[0])Copy the code

Recursive implementation:

function deepFirstSearch(node,nodeList) { if (node) { nodeList.push(node); var children = node.children; for (var i = 0; i < children.length; I ++) // deepFirstSearch(children[I],nodeList); } return nodeList; }Copy the code

For a more obvious comparison, post the previous BFS solution:

function breadthFirstSearch(node) {  
    var nodes = [];  
    if (node != null) {  
        var queue = [];  
        queue.unshift(node); // 将初始节点放入队中
        while (queue.length != 0) {
            var item = queue.shift(); // 提取队首元素
            nodes.push(item);
            var children = item.children; 
            for (var i = 0; i < children.length; i++) // 遍历全部子元素
                queue.push(children[i]);  // 推入队中
        }  
    }  
    return nodes;  
}

breadthFirstSearch(document.getElementsByTagName("body")[0])
Copy the code

Recursive implementation:

function breadthFirstSearch(node) { var nodes = []; var i = 0; if (! (node == null)) { nodes.push(node); breadthFirstSearch(node.nextElementSibling); // priority traversal of sibling nodes node = nodes[i++]; breadthFirstSearch(node.firstElementChild); } return nodes; }Copy the code

To sum up, remember: DFS-stack, BFs-queue;

Let’s do a quick one: the maximum depth of a binary tree

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example: Given a binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 returns its maximum depth of 3.Copy the code

If the node is null, the height is 0, so return 0. If the node is not empty, the maximum height of the left and right subtrees is calculated respectively, and the value is returned by adding 1 to represent the height of the current node.

Recursive solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) {
        return 0;
    } else {
        const left = maxDepth(root.left);
        const right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
};
Copy the code

Time complexity: O(n)

Recursive solution of binary tree, YYDS!

BFS and DFS are important algorithms. BFS focuses on queues and DFS focuses on recursion. They have a lot of room to play in search field.

BFS is often used to find a single shortest route, and its characteristic is “the best solution is found”, while DFS is used to find all solutions. Its space efficiency is high, and the found solution is not necessarily the best solution, and the whole search must be recorded and completed, so in general, deep search requires very efficient pruning. What is pruning in algorithms?

OK, that’s it.

I am Anthony Digger, the public account of the same name, day arch a death, day dig a gold, see you tomorrow ~