中等

问题描述

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

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

示例 2：

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

提示:

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

深度优先搜索

对于每棵子树，它的子树元素和等于子树根节点的值加上左右子树的元素和，因此我们可以使用深度优先搜索来计算每棵子树的元素和，从下往上汇总，用哈希表记录各棵子树的元素和的出现次数，并记录最大值 $max$，最后遍历哈希表，找出出现次数为 $max$ 的元素和。

/**
 * 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 = new Map()
  let max = 0
  const dfs = (node) => {
    if (!node) return 0
    const left = dfs(node.left)
    const right = dfs(node.right)
    const sum = left + right + node.val
    const cnt = (map.get(sum) || 0) + 1
    map.set(sum, cnt)
    max = Math.max(max, cnt)
    return sum
  }
  dfs(root)
  let res = []
  for (const [key, val] of map.entries()) {
    if (val === max) res.push(key)
  }
  return res
}

• 时间复杂度：$O(n)$，需要对树进行一次深度优先搜索。
• 空间复杂度：$O(n)$，需要创建一个哈希表记录元素和的出现次数。