关于leetcode:508出现次数最多的子树元素和-算法leetcode附思维导图-全部解法300题

零 题目：算法（leetcode，附思维导图 + 全副解法）300 题之（508）呈现次数最多的子树元素和

一 题目形容

二 解法总览（思维导图）

三 全副解法

1 计划 1

1)代码：

// 计划 1“本人。后续遍历法”。// 用时：14 分钟。// 思路：// 1）状态初始化：resMap = new Map()。// 2）调用递归函数 updateRootValByDfs(root)。// 3）求得 呈现次数最多的子树元素和 resMaxCount = getMaxCountByMap(resMap)。// 4）若 以后值（即 key）呈现的次数 val 与 resMaxCount，// 则 将 val 放入 resList 中。// 5）返回后果 resList。var findFrequentTreeSum = function(root) {const updateRootValByDfs = (curRoot = null) => {
        // 1）递归进口
        if (!curRoot) {return;}
        const {left, right} = curRoot;
        if (!left && !right) {if (resMap.has(curRoot.val)) {resMap.set(curRoot.val, resMap.get(curRoot.val) + 1);
            }
            else {resMap.set(curRoot.val, 1);
            }
            return;
        }

        // 2）递归主体
        // 2.1）先更新 left 节点上的 val。updateRootValByDfs(left);
        // 2.2）接着更新 right 节点上的 val。updateRootValByDfs(right);
        // 2.3）最初更新 curRoot 节点上的 val。if (left) {curRoot.val += (left.val);
        }
        if (right) {curRoot.val += (right.val);
        }

        if (resMap.has(curRoot.val)) {resMap.set(curRoot.val, resMap.get(curRoot.val) + 1);
        }
        else {resMap.set(curRoot.val, 1);
        }
    };
    const getMaxCountByMap = (map = new Map()) => {
        let resMaxCount = Number.NEGATIVE_INFINITY;

        for (const [key, val] of map) {resMaxCount = Math.max(resMaxCount, val);
        }

        return resMaxCount;
    };

    // 边界（依据提醒，如下代码可疏忽）if (!root) {return [];
    }

    // 1）状态初始化：resMap = new Map()。let resMap = new Map();

    // 2）调用递归函数 updateRootValByDfs(root)。updateRootValByDfs(root);

    // 3）求得 呈现次数最多的子树元素和 resMaxCount = getMaxCountByMap(resMap)。let resMaxCount = getMaxCountByMap(resMap),
        resList = [];
    
    // 4）若 以后值（即 key）呈现的次数 val 与 resMaxCount，// 则 将 val 放入 resList 中。for (const [key, val] of resMap) {if (val === resMaxCount) {resList.push(key);
        }
    }

    // 5）返回后果 resList。return resList;
};

2 计划 2

1)代码：

// 计划 2“官网。深度优先遍历法（实质：跟本人的计划 1 大体上是一样的）”。// 参考：// 1）https://leetcode.cn/problems/most-frequent-subtree-sum/solution/chu-xian-ci-shu-zui-duo-de-zi-shu-yuan-s-kdjc/

// 思路：// 1）状态初始化：esMap = new Map(), resMaxCount = Number.NEGATIVE_INFINITY。// 2）调用递归函数 dfs(root)。// 3）若 以后值（即 key）呈现的次数 val 与 resMaxCount，// 则 将 val 放入 resList 中。// 4）返回后果 resList。var findFrequentTreeSum = function(root) {const dfs = (curRoot = null) => {
        // 1）递归进口。if (!curRoot) {return 0;}

        // 2）递归主体。const {val, left, right} = curRoot,
            sum = val + dfs(left) + dfs(right);
        
        // 2.1）不断更新 resMap、resMaxCount 的值。resMap.set(sum, (resMap.get(sum) || 0) + 1);
        resMaxCount = Math.max(resMaxCount, resMap.get(sum));

        // 2.2）返回以后 sum 值！！return sum;
    };

    // 1）状态初始化：esMap = new Map(), resMaxCount = Number.NEGATIVE_INFINITY。let resMap = new Map(),
        resMaxCount = Number.NEGATIVE_INFINITY;

    // 2）调用递归函数 dfs(root)。dfs(root);

    // 3）若 以后值（即 key）呈现的次数 val 与 resMaxCount，// 则 将 val 放入 resList 中。let resList = [];
    for (const [key, val] of resMap) {if (val === resMaxCount) {resList.push(key);
        }
    }

    // 4）返回后果 resList。return resList;
};

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少，一个致力于编写 极简、但齐全题解（算法 ）的博主。
专一于 一题多解、结构化思维，欢送一起刷穿 LeetCode ~