This article introduces BFS (Breadth-first traversal) and then uses BFS to solve some problems.

Frame thinking is important!!

BFS code framework

Data structure used: queue (QUE) Javascript emulates que: unshift/push

// Storage structure
// {val,left,right}
function bfs(root) {
  	// The operation that responds when an empty tree is passed in
  	if (root == null) return 0;
  	const que = [];
  
  	while(que.length) {
      let sz = que.length;
      for(let i = 0; i < sz; ++i ) {
        let cur = que.shift();
        // The current node, where the operation is performed
        
        if(cur.left ! = =null){
          que.push(cur);
        }   
        if(cur.right! = =null) { que.push(cur); }}}}Copy the code

Common topic

  1. Binary tree level traversal

    /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var levelOrder = function(root) {
    if (root == null) return [];
    const que = [],result = [];
    que.push(root);
    while(que.length) {
        let size = que.length;
        for(let i = 0; i < size; ++i) {let cur = que.shift();
            result.push(cur.val);
            if(cur.left ! = =null ) que.push(cur.left);
            if(cur.right ! = =null) que.push(cur.right)
         }
    }
    return result;
};
Copy the code

  2. Find the maximum depth of binary tree

    /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var maxDepth = function(root) {

    if (root == null) return 0;
    const que = [],depthArray = [];
    que.push(root);

    let depth = 1;
    // When the queue is not empty
    while(que.length ! = =0) {
        let size = que.length;
        // Layer by layer

        for (let i = 0; i < size; ++i) {
            let cur = que.shift();
            // // encounters the leaf node
            if (cur.left == null && cur.right == null) depthArray.push(depth);

            if(cur.left ! = =null) que.push(cur.left);
            if(cur.right ! = =null) que.push(cur.right);
        }
        // Depth is increased by 1 after traversing a layer
        depth++;
    }
    return Math.max.apply(Math,depthArray);
};
Copy the code

  3. Find the minimum depth of binary tree

    Here the minimum depth is equivalent to hitting the first leaf node, because the shallowest leaf node is always traversed first.

    /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var minDepth = function(root) {

    if (root == null) return 0;
    const que = [];
    que.push(root);

    let depth = 1;
    // When the queue is not empty
    while(que.length ! = =0) {
        let size = que.length;
        // Layer by layer

        for (let i = 0; i < size; ++i) {
            let cur = que.shift();
            // // encounters the leaf node
            if (cur.left == null && cur.right == null) return depth;

            if(cur.left ! = =null) que.push(cur.left);
            if(cur.right ! = =null) que.push(cur.right);
        }
        // Depth is increased by 1 after traversing a layer
        depth++;
    }
    return depth;
};
Copy the code

Conclusion:

As a BFS framework shows, once you have a similar framework, you can solve a class of problems, as long as you get the framework right, the rest is the details. Solving problems is especially important to develop frame thinking.

Attached screenshot