当前位置： 面试刷题>> 具有最大平均数的子树 (经典算法题500道)
### 题目描述
给定一个无向树（每个节点最多有一个父节点，但可以有多个子节点），树的节点上带有权重（可以是正数、负数或零）。你的任务是找到树中具有最大平均权重的子树。子树是指树中的一个节点及其所有后代组成的树结构。
平均权重定义为子树中所有节点的权重之和除以子树中的节点数量（包括该子树的根节点）。
### 示例
考虑以下树结构，每个节点旁边的数字表示其权重：
```
1
/ \
2 -3
/ \
4 5
```
- 子树 `{1}` 的平均权重为 `1/1 = 1`
- 子树 `{2, 4, 5}` 的平均权重为 `(2+4+5)/3 = 3.67`
- 子树 `{1, 2, 4, 5}` 的平均权重为 `(1+2+4+5)/4 = 3`
- 子树 `{1, -3}` 的平均权重为 `(1-3)/2 = -1`
- 子树 `{-3}` 的平均权重为 `-3/1 = -3`
因此，具有最大平均权重的子树是 `{2, 4, 5}`，其平均权重为 3.67。
### PHP 代码示例
```php
class TreeNode {
public $val;
public $children;
function __construct($val = 0, $children = []) {
$this->val = $val;
$this->children = $children;
}
}
function findSubtreeWithMaxAverage($root) {
$maxAvg = PHP_INT_MIN;
$maxSubtree = null;
function dfs($node, &$sum, &$count, &$maxAvg, &$maxSubtree) {
if (!$node) return [0, 0];
$nodeSum = $node->val;
$nodeCount = 1;
foreach ($node->children as $child) {
[$childSum, $childCount] = dfs($child, $sum, $count, $maxAvg, $maxSubtree);
$nodeSum += $childSum;
$nodeCount += $childCount;
}
$avg = $nodeSum / $nodeCount;
if ($avg > $maxAvg) {
$maxAvg = $avg;
$maxSubtree = $node;
}
return [$nodeSum, $nodeCount];
}
dfs($root, $sum, $count, $maxAvg, $maxSubtree);
// 返回最大平均权重的子树根节点，或者根据需要返回其他信息
return $maxSubtree;
}
// 示例使用
$root = new TreeNode(1);
$root->children = [
new TreeNode(2, [
new TreeNode(4),
new TreeNode(5)
]),
new TreeNode(-3)
];
$result = findSubtreeWithMaxAverage($root);
// 假设有方法打印树节点，这里仅返回根节点作为示例
echo "Root of the subtree with max average: " . $result->val;
```
注意：由于PHP标准库中没有直接表示树结构的类，上述代码自定义了一个`TreeNode`类来模拟。
### Python 和 JavaScript 代码示例
由于篇幅限制，Python 和 JavaScript 的实现逻辑与 PHP 类似，但语言语法会有所不同。在 Python 中，你可以使用类和列表来模拟树和子节点。在 JavaScript 中，你可以使用对象和数组来实现相似的结构。这些语言都有更丰富的库来处理数据结构，但基本逻辑（深度优先搜索和记录最大平均值）是相似的。
**码小课网站中有更多相关内容分享给大家学习**，包括更高效的树遍历算法、递归与迭代实现、以及其他数据结构和算法的高级主题。