当前位置： 面试刷题>> 出现频率最高的子树和 (经典算法题500道)
### 题目描述补充
**题目：出现频率最高的子树和**
给定一个二叉树，树的每个节点上都含有一个整数值。我们定义子树和为该节点本身的值加上其所有子节点的值之和。你需要找出这棵树中所有不同子树和中出现频率最高的那个子树和，并返回其出现频率。如果有多个子树和的频率相同且都是最高的，则返回其中任意一个即可。
**注意**：
- 树中的节点数不会超过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 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课网站中有更多相关内容分享给大家学习**，包括数据结构、算法、面试技巧等，欢迎访问学习！