1. 题目描述

给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

示例 1：

  1. 输入:
  2.   5
  3.  /  \
  4. 2   -3
  5. 返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2：

  1. 输入：
  2.   5
  3.  /  \
  4. 2   -5
  5. 返回 [2]，只有 2 出现两次，-5 只出现 1 次。

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

2. 解题思路

这道题和二叉树的众数那道题是一样的思路：

  • 首先，先遍历出一次树， 求所有节点的子树和
  • 在遍历的过程中，使用map来记录每个元素出现的次数
  • 遍历完成之后，遍历map，找出次数最多的和，放在res中即可

复杂度分析：

  • 时间复杂度：O(n)，其中n是这棵树的节点数量，我们需要遍历整棵树，来求每个节点的子树和。

  • 空间复杂度：O(n)，其中n是这棵树的节点数量，这里需要的是递归的栈空间的空间代价。

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val) {
    4. *     this.val = val;
    5. *     this.left = this.right = null;
    6. * }
    7. */
    8. /**
    9. * @param {TreeNode} root
    10. * @return {number[]}
    11. */
    12. var findFrequentTreeSum = function(root) {
    13.   let map = {}, res = [], max = 0
    15.   const calcuSum = (root) => {
    16.       if(!root){
    17.           return 0
    18.       }
    19.       let left = calcuSum(root.left)
    20.       let right = calcuSum(root.right)
    22.       let sum = left + right + root.val
    23.       // 将当前节点赋值为其所有子节点的和，方便后面进行计算
    24.       root.val = sum
    25.       map[sum] ? map[sum] += 1 : map[sum] = 1
    26.       return root.val
    27.   }
    28.   calcuSum(root)
    30.   for(let key in map){
    31.       if(map[key] === max){
    32.           res.push(key)
    33.       }
    34.       if(map[key] > max){
    35.           max = map[key]
    36.           res = [key]
    37.       }
    38.   }
    39.   return res
    40. };

    4. 提交结果

    image.png