[2022-06-19]508. 出现次数最多的子树元素和👋树👋深度优先搜索👋哈希表👋二叉树

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/most-frequent-subtree-sum

难度: Medium
标签: 树 深度优先搜索 哈希表 二叉树

[dreamjean]

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

Description

Difficulty: 中等

Related Topics: 树, 深度优先搜索, 哈希表, 二叉树

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

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

示例 1：

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

示例 2：

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

提示:

• 节点数在 [1, 10⁴] 范围内
• -10⁵ <= Node.val <= 10⁵

Solution

Language: JavaScript

思路：后序遍历

• 使用哈希表记录每个子树元素和出现的次数
• 然后从哈希表获取最大次数
• 最后再遍历哈希表找出最大次数的所有元素

/**
 * 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 cnt = {};

    const dfs = node => {
        if (!node) return 0;
        
        const s = node.val + dfs(node.left) + dfs(node.right);
        cnt[s] ? cnt[s]++ : cnt[s] = 1; 
        
        return s;
    }

    dfs(root);
    let maxCount = Math.max(...Object.values(cnt));

    return Object
        .entries(cnt)
        .reduce((arr, [num, count]) => {
            if (count === maxCount) arr.push(+num);

            return arr;
        }, [])
};

[webVueBlog]

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

Description

Difficulty: 中等

Related Topics: 树, 深度优先搜索, 哈希表, 二叉树

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

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

示例 1：

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

示例 2：

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

提示:

• 节点数在 [1, 10⁴] 范围内
• -10⁵ <= Node.val <= 10⁵

Solution

Language: JavaScript

/**
 * 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) {

};