508. 出现次数最多的子树元素和

508. 出现次数最多的子树元素和

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3] 输出: [2,-3,4]
示例 2：

输入: root = [5,2,-5] 输出: [2]

提示:

• 节点数在 [1, 104] 范围内
• -105 <= Node.val <= 105

思路

按题意模拟即可，两层 dfs，一次遍历所有节点，一次计算所有节点的子树和，同时更新出现次数计数，并加入结果中，最后过滤 map 输出即可。

解答

/**
 * 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 findFrequentTreeSum = function (root) {
  const map = {};
  let max = -Infinity;
  const visit = (node) => {
    if (!node) return 0;
    const sum = node.val + visit(node.left) + visit(node.right);
    if (map[sum]) map[sum]++;
    else map[sum] = 1;
    max = Math.max(map[sum], max);
    return sum;
  };

  visit(root);
  return [...Object.entries(map)]
    .filter(([key, val]) => val === max)
    .map(([key]) => key);
};