【JavaScript】LeetCode：56-60

文章目录

56 路径总和Ⅲ
57 二叉树的最近公共祖先
58 二叉树中的最大路径
59 岛屿数量
60 腐烂的橘子

56 路径总和Ⅲ

在这里插入图片描述

递归
遍历每个节点所有可能的路径。pathSum()：返回所有节点满足条件的路径数目，traversal()：返回当前遍历节点满足条件的路径数目。

/*** 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)* }*/var traversal = function(root, targetSum){if(root == null){return 0;}let res = 0;if(root.val == targetSum){res += 1;//return res; 不能立刻返回，下面可能还有结果(一正一负)}res += traversal(root.left, targetSum - root.val);res += traversal(root.right, targetSum - root.val);return res;
}/*** @param {TreeNode} root* @param {number} targetSum* @return {number}*/
var pathSum = function(root, targetSum) {if(root == null){return 0;}let ans = 0;ans += traversal(root, targetSum);ans += pathSum(root.left, targetSum);ans += pathSum(root.right, targetSum);return ans;
};

57 二叉树的最近公共祖先

在这里插入图片描述

递归 + 后序遍历（自底向上查找）
情况1：如果找到一个节点，左子树出现节点p，右子树出现节点q，或右子树出现节点p，左子树出现节点q，那么该节点为节点p和q的最近公共祖先。
情况2：节点p或q本身就是最近公共祖先。
如果遇到节点p或q就返回本身节点；如果一直没有遇到节点p或q，直到叶子节点，则返回null。
遍历左右子树，用left和right承接返回结果。
如果left和right都不为空，说明此时root就是最近公共节点。
如果left为空，right / left不为空，就返回right / left，说明目标节点是通过right / left返回的。

/*** Definition for a binary tree node.* function TreeNode(val) {*     this.val = val;*     this.left = this.right = null;* }*/
/*** @param {TreeNode} root* @param {TreeNode} p* @param {TreeNode} q* @return {TreeNode}*/
var lowestCommonAncestor = function(root, p, q) {var traversal = function(root, p, q){if(root == null){return null;}if(root == p || root == q){return root;}let left = traversal(root.left, p, q);let right = traversal(root.right, p, q);if(left != null && right != null){return root;}else if(left == null && right != null){return right;}else if(left != null && right == null){return left;}else{return null;}}return traversal(root, p, q);
};

58 二叉树中的最大路径

在这里插入图片描述

递归 + 后序遍历
以节点root为根的最大路径和sum = root.val + 左子树的返回值 + 右子树的返回值
每个节点root的返回结果 = root.val + max(左子树的返回值，右子树的返回值)
不断更新结果maxSum = max(maxSum，sum)
最后结果返回max(maxSum，0)，例如：如果右子树是负数，那路径就不需要走右子树了，因为路径和会越加越小。

/*** 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 maxPathSum = function(root) {var traversal = function(root){if(root == null){return  0;}let left = traversal(root.left);let right = traversal(root.right);let sum = root.val + left + right;maxsum = Math.max(maxsum, sum);res = root.val + Math.max(left, right);return Math.max(res, 0);}let maxsum = -Number.MAX_VALUE;traversal(root);return maxsum;
};

59 岛屿数量

在这里插入图片描述

DFS
主函数：numIslands，双层for循环遍历网格点，如果该网格点为岛屿且没有被访问过，调用递归函数。
递归函数：dfs，网格点遍历上、右、下、左资格方向，若该方向上的点越界或已经被访问，continue；否则判断该方向上的点是否为岛屿，若为岛屿则继续递归。

/*** @param {character[][]} grid* @return {number}*/
var numIslands = function(grid) {var dfs = function(grid, vis, x, y){let dirt = [[1, 0], [0, 1], [-1, 0], [0, -1]];for(let i = 0; i < 4; i++){let x_ = x + dirt[i][0];let y_ = y + dirt[i][1];if(x_ < 0 || x_ >= n || y_ < 0 || y_ >= m || vis[x_][y_] == 1){continue;}if(grid[x_][y_] == '1'){vis[x_][y_] = 1;dfs(grid, vis, x_, y_);}}}let n = grid.length;let m = grid[0].length;let vis = Array(n).fill(null).map(() => Array(m).fill(0));let res = 0;for(let i = 0; i < n; i++){for(let j = 0; j < m; j++){if(!vis[i][j] && grid[i][j] == '1'){dfs(grid, vis, i, j);res += 1;}}}return res;
};

60 腐烂的橘子

在这里插入图片描述

BFS
双层for循环遍历单元格，记录新鲜橘子的个数fresh，并将腐烂的橘子记录到队列queue中。
逐层遍历队列中的元素，每遍历一层分钟数 + 1，直到队列为空。
遍历腐烂橘子的四个方向：上、右、下、左，若该方向上的橘子是新鲜的，则新鲜橘子个数 - 1，变为腐烂橘子。
若最后所有橘子都变成了腐烂的，则返回分钟数，否则说明还存在新鲜橘子，该橘子永远都不能变为腐烂橘子，返回 -1。
最后返回的分钟数应该 - 1，因为刚开始处理队列中第一个元素时，就已经 + 1了，因此结果也多加了1。

/*** @param {number[][]} grid* @return {number}*/
var orangesRotting = function(grid) {let n = grid.length;let m = grid[0].length;let dirt = [[1, 0], [0, 1], [-1, 0], [0, -1]];let queue = [];let fresh = 0;let res = 0;for(let i = 0; i < n; i++){for(let j = 0; j < m; j++){if(grid[i][j] == 1){fresh += 1;}else if(grid[i][j] == 2){queue.push([i, j]);}}}if(fresh == 0){return 0;}while(queue.length){res += 1;let temp = queue;queue = [];for(let [x, y] of temp){for(let d = 0; d < 4; d++){let x_ = x + dirt[d][0];let y_ = y + dirt[d][1];if(x_ >= 0 && x_ < n && y_ >= 0 && y_ < m && grid[x_][y_] == 1){queue.push([x_, y_]);grid[x_][y_] = 2;fresh -= 1;}}}}return fresh? -1: res - 1;
};