DEV Community 👩‍💻👨‍💻

Cover image for 代码随想录day15 | BFS template LC problems, 226.Invert Binary Tree, 101. Symmetric Tree
Ming
Ming

Posted on

代码随想录day15 | BFS template LC problems, 226.Invert Binary Tree, 101. Symmetric Tree

Leetcode problems can be resolved by BFS template.

🔷首先BFS模版先得掌握且背熟🔷:

const levelOrder = (root) => {
  if (root === null) return [];

  let visited = [];
  let queue = [root];

  while (queue.length) {
    let len = queue.length; // 记录当前层级节点数
    let curLevel = []; //curLevel用于存放每一层的节点

    /* queue弹出(shift)len个, 并且开始加(push)下一层的节点 
      (每进一次forloop就是遍历每一层的node) */
    for (let i = 0; i < len; i++) {
      let node = queue.shift();
      curLevel.push(node.val);
      //存放当前层的下一层的节点到queue
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    visited.push(curLevel); //把每一层的结果放到结果数组
  }

  return visited;
};
Enter fullscreen mode Exit fullscreen mode

现在用这个bfs模版去做下面这些题目, 基本上是在每层level上改动,所以要明确每次进1次while就是代表进入新的一层, 进去1次forloop就是代表遍历当前层的所有的节点们

var levelOrderBottom = function(root) {
    if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let curLevel = [];

      for(let i=0; i<len; i++){
        let node = queue.shift();
        curLevel.push(node.val);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

      visited.push(curLevel)
    }

    return visited.reverse();  // 😀 difference is here
};
Enter fullscreen mode Exit fullscreen mode
var rightSideView = function(root) {
     if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let curLevel = [];

      for(let i=0; i<len; i++){
        let node = queue.shift();
        // 😀 difference is here
        if(i === len-1){
          curLevel.push(node.val);
        }
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

      visited.push(curLevel)
    }

    return visited;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 637 - Average of Levels in Binary Tree

var averageOfLevels = function(root) {
    if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let sum = 0;  //😀 difference is here

      for(let i=0; i<len; i++){
        let node = queue.shift();
        sum+=node.val;  // 😀 difference is here
        if(i===len-1){  // 😀 difference is here
          visited.push(sum/len)
        }
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

    }

    return visited;
};
Enter fullscreen mode Exit fullscreen mode

或者这个更直观:

var averageOfLevels = function(root) {
     if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let curLevel = [];

      for(let i=0; i<len; i++){
        let node = queue.shift();
        curLevel.push(node.val);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }
      // 😀 difference is here
      const average = curLevel.reduce((acc,cur)=>acc+cur)/len
      visited.push(average);
    }

    return visited;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 429 - N-ary Tree Level Order Traversal

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */

var levelOrder = function(root) {
        if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let curLevel = [];

      for(let i=0; i<len; i++){
        let node = queue.shift();
        curLevel.push(node.val);
        // 😀 difference is here
        for(let child of node.children){
          queue.push(child)
        }
      }

      visited.push(curLevel)
    }

    return visited;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 515 - Find Largest Value in Each Tree Row

var largestValues = function(root) {
    if(!root) return [];

    let visited = [];
    let queue = [root];

    while(queue.length){
      let len = queue.length;
      let max = -Infinity;  // 😀 difference is here

      for(let i=0; i<len; i++){
        let node = queue.shift();
        max= Math.max(max, node.val); // 😀 difference is here
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

      visited.push(max) // 😀 difference is here
    }

    return visited;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 116 - Populating Next Right Pointers in Each Node
leetcode 117 - Populating Next Right Pointers in Each Node II

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */

//只不过在单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点就可以了

var connect = function (root) {
  if (!root) return root;
  let queue = [root];

  while (queue.length) {
    let len = queue.length; // 记录当前层级节点数

    for (let i = 0; i < len; i++) {
      let node = queue.shift();
      // 😀 difference is here
      if (i < len - 1) {
        node.next = queue[0];
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return root;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 104 - Maximum Depth of Binary Tree

这道题要重点掌握DFS-recursion-postorder的解法和BFS解法

var maxDepth = function(root) {
   if(!root) return [];

    let queue = [root];
    let depth = 0;  // 😀 difference is here

    while(queue.length){
      let len = queue.length;
      depth++; // 😀 difference is here

      for(let i=0; i<len; i++){
        let node = queue.shift();
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

    }

    return depth; // 😀 difference is here
};
Enter fullscreen mode Exit fullscreen mode

or solve by DFS:

var maxDepth = function(root) {

   const helper = (node) => {
      if(!node) return 0;

      const leftTreeDepth = helper(node.left);
      const rightTreeDepth = helper(node.right)
      return 1 + Math.max(leftTreeDepth, rightTreeDepth)
   }

   return helper(root);
};
Enter fullscreen mode Exit fullscreen mode

leetcode 111 - Minimum Depth of Binary Tree

这道题BFS和DFS解法都要掌握,但是注意dfs写起来容易掉进一个陷阱:处理左右孩子不为空的逻辑要写上

var minDepth = function(root) {

  if(!root) return [];

    let queue = [root];
    let min_depth = 0;  // 😀 difference is here

    while(queue.length){
      let len = queue.length;
      min_depth ++; // 😀 difference is here

      for(let i=0; i<len; i++){
        let node = queue.shift();
        // 😀 (在遇见的第一个leaf节点上),则该节点深度最小
        if(!node.left && !node.right) return min_depth
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

    }

    return min_depth;

};
Enter fullscreen mode Exit fullscreen mode

OR slove by DFS:

var minDepth = function (root) {

  const getDepth = (node) => {
    if (!node) return 0; 

    let leftTreeDepth = getDepth(node.left); 
    let rightTreeDepth = getDepth(node.right); 

    /* 处理左右孩子不为空: */

    //如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度
    if (!node.left && node.right) return 1 + rightTreeDepth; 
    //右子树为空,左子树不为空,最小深度是 1 + 左子树的深度
    if (node.left && !node.right) return 1 + leftTreeDepth;
    //左右子树都不为空,返回左右子树深度最小值 + 1
    return 1 + Math.min(leftTreeDepth, rightTreeDepth);
  };

  return getDepth(root);
};
Enter fullscreen mode Exit fullscreen mode

leetcode 226 - Invert Binary Tree

翻转一棵二叉树
Image description

这道题一定要掌握DFS递归法,preorder, postorder都🉑️

DFS - Recursion:

var invertTree = function (root) {
  if (!root) return root;

  // 参数: 子树, 没返回值
  const helper = (node) => {
    if (!node) return;

    //invert node 的左右节点
    [node.left, node.right] = [node.right, node.left]; 
    if (node.left)  helper(node.left);
    if (node.right) helper(node.right);
  };

  helper(root);
  return root;
};
Enter fullscreen mode Exit fullscreen mode

DFS - iteration:

var invertTree = function (root) {
  if (!root) return root;

  let stack = [root];

  while (stack.length) {
    let curr = stack.pop();

    if (!curr) {
      let node = stack.pop();
      //invert node 的左右节点
      [node.left, node.right] = [node.right, node.left]; 
      continue;
    }

    /* preorder: 中左右, then入栈顺序为:右坐中 */
    if (curr.right) stack.push(curr.right);
    if (curr.left) stack.push(curr.left);
    stack.push(curr);
    stack.push(null);
  }

  return root;
};
Enter fullscreen mode Exit fullscreen mode

BFS:

var invertTree = function (root) {
  if (!root) return root;

  let queue = [root];

  while (queue.length) {
    node = queue.shift();
     //invert node 的左右节点
    [node.left, node.right] = [node.right, node.left];
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
};

Enter fullscreen mode Exit fullscreen mode

leetcode 101 - Symmetric Tree

给定一个二叉树,检查它是否是镜像对称的。
Image description

这道题一定要掌握DFS递归法, post order

var isSymmetric = function(root) {

    // 参数:左右子树, 返回值:boolean
    const helper = (left, right) => {
       if(!left && right) return false
       else if (left && !right) return false
       else if (!left && !right) return true;
       else if (left.val !== right.val) return false;

      //when left.val ===right.val, start to recursion
      const isOutsideSame = helper(left.left, right.right);
      const isInsideSame = helper(left.right, right.left);
      return isOutsideSame && isInsideSame //🀄️

    }

    return helper(root.left, root.right);
};

Enter fullscreen mode Exit fullscreen mode

今日总结:

  1. ✅ BFS模型很扛打,掌握并背过
  2. ✅ 使用dfs递归时候要先好好思考
    • 递归函数的输入和输出是什么?
    • 终止条件是什么?
    • 单层递归的逻辑?

Top comments (0)

Classic DEV Post from 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!