哈希映射和递归：求解《508. 出现次数最多的子树元素和》

var findFrequentTreeSum = function(root) {
  const map = new Map
  let maxCnt = 0
  const d = n => {
    if (n === null) return 0
    const sum = d(n.left) + d(n.right) + n.val
    const cnt = (map.get(sum) || 0) + 1
    if (cnt > maxCnt) maxCnt = cnt
    map.set(sum, cnt)
    return sum
  }
  d(root)
  const r = []
  map.forEach((cnt, sum) => {
    if (cnt === maxCnt) r.push(sum)
  })
  return r
};

function findFrequentTreeSum(root: TreeNode | null): number[] {
  const map = Object.create(null)
  let maxCnt = 0
  const d = n => {
    if (n === null) return 0
    const sum = d(n.left) + d(n.right) + n.val
    const cnt = (map[sum] || 0) + 1
    if (cnt > maxCnt) maxCnt = cnt
    map[sum] = cnt
    return sum
  }
  d(root)
  const r = []
  for (const [sum, cnt] of Object.entries(map)) {
    if (cnt === maxCnt) r.push(sum)
  }
  return r
};

func findFrequentTreeSum(root *TreeNode) []int {
  m, maxCnt, r := map[int]int{}, 0, []int{}
  var d func(n *TreeNode) int
  d = func(n *TreeNode) int {
    if n == nil {
      return 0
    }
    sum := d(n.Left) + d(n.Right) + n.Val
    cnt := m[sum] + 1
    if cnt > maxCnt {
      maxCnt = cnt
    }
    m[sum] = cnt
    return sum
  }
  d(root)
  for sum, cnt := range m {
    if cnt == maxCnt {
      r = append(r, sum)
    }
  }
  return r
}

class Solution {
  private $map = array();
  private $maxCnt = 0;
  function findFrequentTreeSum($root) {
    $this->d($root);
    $r = [];
    foreach ($this->map as $sum => $cnt) {
      if ($cnt === $this->maxCnt) $r []= $sum;
    }
    return $r;
  }
  function d($n) {
    if ($n === null) return 0;
    $sum = $this->d($n->left) + $this->d($n->right) + $n->val;
    $cnt = $this->map[$sum] + 1;
    if ($cnt > $this->maxCnt) $this->maxCnt = $cnt;
    $this->map[$sum] = $cnt;
    return $sum;
  }
}

class Solution:
  def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
    dict, maxCnt, r = {}, 0, []
    def d(n):
      nonlocal maxCnt
      if n == None: return 0
      sum = d(n.left) + d(n.right) + n.val
      cnt = dict.setdefault(sum, 0) + 1
      if cnt > maxCnt: maxCnt = cnt
      dict[sum] = cnt
      return sum
    d(root)
    for sum, cnt in dict.items():
      if cnt == maxCnt: r.append(sum)
    return r

class Solution {
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  int maxCnt = 0;
  public int[] findFrequentTreeSum(TreeNode root) {
    d(root);
    List<Integer> l = new ArrayList<Integer>();
    for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
      if (entry.getValue() == maxCnt) l.add(entry.getKey());
    }
    int n = l.size();
    int[] r = new int[n];
    for (int i = 0; i < n; i++) {
      r[i] = l.get(i);
    }
    return r;
  }
  public int d(TreeNode n) {
    if (n == null) return 0;
    int sum = d(n.left) + d(n.right) + n.val;
    int cnt = map.getOrDefault(sum, 0) + 1;
    if (cnt > maxCnt) maxCnt = cnt;
    map.put(sum, cnt);
    return sum;
  }
}

class Solution {
public:
  unordered_map<int, int> map;
  int maxCnt;
  vector<int> findFrequentTreeSum(TreeNode* root) {
    d(root);
    vector<int> r;
    for (auto &[sum, cnt] : map) {
      if (cnt == maxCnt) r.emplace_back(sum);
    }
    return r;
  }
  int d(TreeNode* n) {
    if (n == nullptr) return 0;
    int sum = d(n->left) + d(n->right) + n->val;
    int cnt = map[sum] + 1;
    if (cnt > maxCnt) maxCnt = cnt;
    map[sum] = cnt;
    return sum;
  }
};

public class Solution {
  Dictionary<int, int> dict = new Dictionary<int, int>();
  int maxCnt = 0;
  public int[] FindFrequentTreeSum(TreeNode root) {
    D(root);
    List<int> r = new List<int>();
    foreach (KeyValuePair<int, int> pair in dict) {
      if (pair.Value == maxCnt) r.Add(pair.Key);
    }
    return r.ToArray();
  }
  public int D(TreeNode n) {
    if (n == null) return 0;
    int sum = D(n.left) + D(n.right) + n.val;
    if (dict.ContainsKey(sum) == false) dict.Add(sum, 0);
    int cnt = dict[sum] + 1;
    if (cnt > maxCnt) maxCnt = cnt;
    dict[sum] = cnt;
    return sum;
  }
}