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;
};
现在用这个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
};
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;
};
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;
};
或者这个更直观：
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;
};
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;
};
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;
};
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;
};
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
};
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
这道题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;
};
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递归法，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;
};
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
给定一个二叉树，检查它是否是镜像对称的。
这道题一定要掌握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);
};
今日总结：
- ✅ BFS模型很扛打，掌握并背过
- ✅ 使用dfs递归时候要先好好思考
- 递归函数的输入和输出是什么？
- 终止条件是什么？
- 单层递归的逻辑?
Top comments (0)