题目描述补充

题目：出现频率最高的子树和

给定一个二叉树，树的每个节点上都含有一个整数值。我们定义子树和为该节点本身的值加上其所有子节点的值之和。你需要找出这棵树中所有不同子树和中出现频率最高的那个子树和，并返回其出现频率。如果有多个子树和的频率相同且都是最高的，则返回其中任意一个即可。

注意：

• 树中的节点数不会超过500。
• 每个节点的值都是整数，范围在 [-10000, 10000] 之间。

示例

假设给定的树如下：

    5
   / \
  2  -5

• 子树和为 2 的有 1 个（单独的节点 2）。
• 子树和为 -5 的有 1 个（单独的节点 -5）。
• 子树和为 2 - 5 = -3 的有 1 个（节点 2 及其右子节点 -5）。
• 子树和为 5 + 2 + (-5) = 2 的有 1 个（整棵树）。

因此，出现频率最高的子树和是 2（出现 1 次）和 -3（出现 1 次），返回其中任意一个的频率 1。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function findFrequentTreeSum($root) {
    $freqMap = [];
    dfs($root, $freqMap);
    $maxFreq = 0;
    $maxSum = null;
    foreach ($freqMap as $sum => $freq) {
        if ($freq > $maxFreq) {
            $maxFreq = $freq;
            $maxSum = $sum;
        }
    }
    return $maxFreq;
}

function dfs($node, &$freqMap) {
    if ($node === null) return 0;
    $sum = $node->val + dfs($node->left, $freqMap) + dfs($node->right, $freqMap);
    $freqMap[$sum] = isset($freqMap[$sum]) ? $freqMap[$sum] + 1 : 1;
    return $sum;
}

// 示例用法
$root = new TreeNode(5);
$root->left = new TreeNode(2);
$root->right = new TreeNode(-5);
echo findFrequentTreeSum($root); // 输出 1

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findFrequentTreeSum(root):
    freq_map = {}
    def dfs(node):
        if not node:
            return 0
        total_sum = node.val + dfs(node.left) + dfs(node.right)
        freq_map[total_sum] = freq_map.get(total_sum, 0) + 1
        return total_sum
    
    dfs(root)
    max_freq = max(freq_map.values())
    return max_freq

# 示例用法
root = TreeNode(5)
root.left = TreeNode(2)
root.right = TreeNode(-5)
print(findFrequentTreeSum(root))  # 输出 1

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function findFrequentTreeSum(root) {
    let freqMap = {};
    function dfs(node) {
        if (!node) return 0;
        let sum = node.val + dfs(node.left) + dfs(node.right);
        if (freqMap[sum]) {
            freqMap[sum]++;
        } else {
            freqMap[sum] = 1;
        }
        return sum;
    }
    dfs(root);
    let maxFreq = 0;
    for (let freq of Object.values(freqMap)) {
        if (freq > maxFreq) {
            maxFreq = freq;
        }
    }
    return maxFreq;
}

// 示例用法
const root = new TreeNode(5);
root.left = new TreeNode(2);
root.right = new TreeNode(-5);
console.log(findFrequentTreeSum(root)); // 输出 1

码小课网站中有更多相关内容分享给大家学习，包括数据结构、算法、面试技巧等，欢迎访问学习！