preface

Recently, when I met with a department of netease, one of the algorithm questions was DFS, depth first traversal, so I plan to comb it this time to practice my skills, and it will be convenient for me to look for it next time.

Must know a variety of solutions, the interview, I was writing recursion, the interview brother asked me if I can use iteration to complete, so a variety of solutions to be able to.

There is an advanced title at the end of the article 🤭

What are the common question types of BFS and DFS?

BFS-DFS questions will be added to GitHub, ideas and code are available, interested partners can play 👇

Data structure -BFS-DFS

BFS & DFS

I suggest you take a look at this zhihu article, which introduces the concept of search idea — DFS & BFS (Basic Foundation)

BFS: Breadth-first search

Simply put, BFS starts at the root node, traverses the tree’s nodes along the width of the tree, and terminates the calculus if a target is found.

DFS: depth-first search

In simple terms, you start at the root node and continue searching down until you reach a leaf node, at which point you backtrack and continue searching in depth for the point you visited.

The basic topic

The following types of questions are sorted according to the order of individual questions, and the degree of difficulty will also be divided for your reference.

The main problem site is 👇

  • The sword refers to offer
  • Power button leetcode

Netease original topic

The title is 👇

const tree = { name: 'root', children: [ { name: 'c1', children: [ { name: 'c11', children: [] }, { name: 'c12', children: [] } ] }, { name: 'c2', children: [ { name: 'c21', children: [] }, { name: 'c22', children: []}}}]] / / depth-first traversal print name / / [' root ', 'c1', 'c11, c12,' c2 ', 'c21', 'c22]Copy the code

Well, when the interview wrote a recursive writing method, netease’s little brother seems to feel dissatisfied, ask, recursive defects, ask me can optimize, well, the face of the time, did not think, he was stupid, down to give stack simulation recursive writing 👇

function solve(root) {
            let stack = [],
                result = [];
            if(! root)return [];
            stack.push(root)
            while(stack.length) {
                let node = stack.pop()
                if(node == null ) continue
                result.push(node.name)
                for(let i = node.children.length-1; i >= 0; i--) {
                    // This is the point of the interview and should be pushed from the back node
                    stack.push(node.children[i])
                }
            }
            return result
        }
Copy the code

Maximum depth of 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.

Link: Force button – maximum depth of binary tree

Example:

Given a binary tree [3,9,20,null,null,15,7],

  	3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

Source: LeetCode link: leetcode-cn.com/problems/ma…

Recursive thinking:

  • Traverse the left node and the right node each time, and then compare the two to get the maximum value
  • So every time I recurse, I increase the depth by 1
var maxDepth = function (root) { if (! root) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 };Copy the code

Non-recursive thinking:

  • BFS, breadth-first traversal
  • The temp array is used to hold all nodes in the upper layer at a time, counting count+1 each time
  • When temp is empty, that’s when it’s a leaf node
var maxDepth = function (root) {
    if(! root)return 0
    let queue = [root],
        res = 0;
    while(queue.length) {
        let temp = []
        for(let i = 0; i < queue.length; i++) {
            if(queue[i].left) temp.push(queue[i].left)
            if(queue[i].right) temp.push(queue[i].right)
        }
        res += 1
        queue = temp
    }
    return res
};
Copy the code

The code point here is ☑️

Minimum depth of binary tree ⭐

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Link: the minimum depth of a binary tree

Example:

Given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its minimum depth of 2

Source: LeetCode link: leetcode-cn.com/problems/mi…

Recursive thinking:

  1. Checks whether the current node is root and empty, and returns 0 if so
  2. When both the left and right nodes of the current node are null, i.e. leaf nodes, this is the target node, minimum depth, return 1
  3. The left node of the current node is not null. Find the depth of the left subtree
  4. The current node right node is not null, find the depth of the right subtree
  5. Comparing the two returns the minimum value of the 3 and 4 conditions, plus 1

A look at the code a thought 👇

var minDepth = function (root) {
    if (root == null) return 0
    if (root.left == null && root.right == null) return 1
    let max = 10000;
    if (root.left) max = Math.min(max, minDepth(root.left))
    if (root.right) max = Math.min(max, minDepth(root.right))
    return max + 1
};
Copy the code

Non-recursive thinking:

  • Traverses each level of the tree, and returns the result when there are no left or right nodes
  • Walk through each layer of nodes, when the stack, a node left and right nodes are empty, that is, find the target node.

Do more BFS, it will be found that the original are set problems 👇

var minDepth = function (root) {
    if(! root)return 0
    let stack = [root],
        ans = 0
    while (stack.length) {
        let temp = []
        ans++
        for (let i = 0; i < stack.length; i++) {
            if (stack[i].left == null && stack[i].right == null) return ans;
            if (stack[i].left) temp.push(stack[i].left)
            if (stack[i].right) temp.push(stack[i].right)
        }
        stack = temp;
    }
    return ans
};
Copy the code

The code point here is ☑️

Hierarchical traversal of binary trees ⭐⭐

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Link: [leetcode] inverts a linked list

Example: binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/re…

Ideas:

  • The easiest way to do this is BFS
  • Each time a layer is traversed, its children are saved as Temp in order
  • Take the result of the child node as the new result, which is que = temp
var levelOrder = function (root) {
    let res = [],
        que = [root];
    if(! root)return []
    while (que.length) {
        let temp = [],
            ans = []
        for (let i = 0; i < que.length; i++) {
            ans.push(que[i].val)
            if (que[i].left) temp.push(que[i].left)
            if (que[i].right) temp.push(que[i].right)
        }
        res.push(ans)
        que = temp
    }
    return res;
};
Copy the code

I didn’t open up the recursion, but I think it’s easy to write.

The code point here is ☑️

Zigzag level traversal of binary trees ⭐⭐

Given a binary tree, return a zigzag hierarchy traversal of its node values. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

Link: 103 Zigzag hierarchy traversal of binary trees

For example, given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the zigzag hierarchy traversal as follows:

[[3], [20,9], [15,7]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi…

BFS routine questions

  • Same idea, but this time it’s the result that needs to be flipped
  • Well, set a flag, check the odd and even case, and flip the answer
var zigzagLevelOrder = function (root) {
    let res = [],
        que = [root],
        flag = 0;
    if(! root)return []
    while (que.length) {
        let temp = [],
            ans = []
        flag++;
        for (let i = 0; i < que.length; i++) {
            ans.push(que[i].val)
            if (que[i].left) temp.push(que[i].left)
            if (que[i].right) temp.push(que[i].right)
        }
        // Check the odd and even case, then flip
        if (flag % 2= = =1) {
            res.push(ans)
        } else {
            res.push(ans.reverse())
        }
        que = temp // push the hierarchy back on the stack
    }
    return res;
};
Copy the code

Click here at 🤭

The longest increasing path in the matrix is ⭐⭐⭐

Given a linked list, swap adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, you need to actually swap nodes.

Link: The longest increasing path in a matrix

Given an integer matrix, find the length of the longest increasing path.

For each cell, you can move up, down, left, and right. You cannot move diagonally or out of bounds.

Example 1:

Input: nums = [[9,9,4], [6,6,8], [2,1,1]]Copy the code

Description: The longest increment path is [1, 2, 6, 9]. Example 2:

Input: nums = [[3,4,5], [3,2,6], [2,2,1]Copy the code

Description: The longest increment path is [3, 4, 5, 6]. Be careful not to move in the diagonal direction.

Source: LeetCode link: leetcode-cn.com/problems/lo…

Thinking 👇

  • DFS + memorized search
  • First of all, you’re at (I, j), and then there are four directions you can go, up, down, left, and right, and all we need to decide is whether it’s legal
  • We’re going to use dx and dy to simulate the four operations up, down, left, and right, which means you can go in four directions
  • So what we need to do is we need to iterate over each of the positions, and what we need to do with the positions that we’ve iterate over, is we need to take it to the next step, which is memorization
  • The difficulty with DFS is how do you prune, how do you optimize, how do you remember these positions

I have not finished writing out, look at others’ ideas 👇

// 0 and 1, 1 and 0, 0 and -1, -1 and 0, four directions
const dx = [0.1.0, -1];
const dy = [1.0, -1.0];
const longestIncreasingPath = (matrix) = > {
    if (matrix.length == 0) return 0;
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = new Array(m);
    for (let i = 0; i < m; i++) dp[i] = new Array(n);
    // Each length must be at least 1
    let res = 1;

    //// DFS coordinates (I,j)
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            res = Math.max(res, dfs(matrix, i, j, m, n, dp)); }}return res;
};

const dfs = (matrix, i, j, m, n, dp) = > {
    // Memory search
    if (dp[i][j]) return dp[i][j];
    let max = 1;

    // The path starting at (I,j) has a minimum length of 1
    for (let k = 0; k < 4; k++) { // Loop four times, so there are four directions to go
        const x = i + dx[k];
        const y = j + dy[k];
        // Determine whether the following coordinates are valid
        // 0<=x && x < m
        // 0 <= y <= n
        if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
            max = Math.max(max, 1+ dfs(matrix, x, y, m, n, dp)); }}// In the current case, we need to find the maximum value of the (I,j) square
    return dp[i][j] = max;
};
Copy the code

Summary of advanced questions

This topic wants to advance, brush the topic that I provide below 👇

DFS

  • The maximum depth of a binary tree

  • The minimum depth of a binary tree

  • Circle of friends

  • Find the final safe state

  • The longest increasing path in a matrix

  • minesweeper

  • randomly

BFS

  • N – tree sequence traversal

  • Sequential traversal of binary trees

  • Minimum height tree

  • minesweeper

Hopefully this article has helped you understand a little DFS, BFS. What is its routine, how to write, I hope you are to throw a brick to attract jade, refueling, UpUpUp.

❤️ thank you

If you find this article helpful:

  1. Click “like” to support it, so that more people can see this content.

  2. Pay attention to the public number front UpUp, regularly push good articles for you.

  3. If you feel good, you can also read TianTian’s recent article (thanks to Digg friends for their encouragement and support 🌹🌹🌹) :

    • Configure WebPack4 from shallow to deep (580+👍)

    • Reinforce your HTTP body of knowledge (860+👍)

    • 21 High-frequency JavaScript handwritten interview questions for Good (580+👍)

    • 18 Browser interview questions (740+👍)

    • 54 JavaScript interview questions (620+👍)