题目描述

给定一个无向树（每个节点最多有一个父节点，但可以有多个子节点），树的节点上带有权重（可以是正数、负数或零）。你的任务是找到树中具有最大平均权重的子树。子树是指树中的一个节点及其所有后代组成的树结构。

平均权重定义为子树中所有节点的权重之和除以子树中的节点数量（包括该子树的根节点）。

示例

考虑以下树结构，每个节点旁边的数字表示其权重：

    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 代码示例

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 中，你可以使用对象和数组来实现相似的结构。这些语言都有更丰富的库来处理数据结构，但基本逻辑（深度优先搜索和记录最大平均值）是相似的。

码小课网站中有更多相关内容分享给大家学习，包括更高效的树遍历算法、递归与迭代实现、以及其他数据结构和算法的高级主题。