【JavaScript】LeetCode：56-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;
};

原文地址：https://blog.csdn.net/weixin_45980065/article/details/142524977

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！