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;
};

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
};
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;
};
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;
};

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;
};
/**
* // 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;
};
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;
};
/**
* // 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;
};

leetcode 104 - Maximum Depth of Binary Tree

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
};

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);
};

leetcode 111 - Minimum Depth of Binary Tree

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;

};

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);
};

## leetcode 226 - Invert Binary Tree

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;
};

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;
};

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;
};

## leetcode 101 - Symmetric Tree

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);
};

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

## Top comments (0)

Classic DEV Post from 2020:

## 🚀⚙️ 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!