零 标题：算法（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 历史文章 - 总览
刷题进度 - LeetCode：545 / 2678 、《剑指offer》：66 / 66
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~
网友评论