文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一棵二叉樹的根節(jié)點 root，找出這棵樹的 每一棵 子樹的 平均值 中的 最大 值。

子樹是樹中的任意節(jié)點和它的所有后代構(gòu)成的集合。

樹的平均值是樹中節(jié)點值的總和除以節(jié)點數(shù)。

示例：

輸入：[5,6,1] 輸出：6.00000 解釋： 以 value = 5 的節(jié)點作為子樹的根節(jié)點，得到的平均值為 (5 + 6 + 1) / 3 = 4。 以 value = 6 的節(jié)點作為子樹的根節(jié)點，得到的平均值為 6 / 1 = 6。 以 value = 1 的節(jié)點作為子樹的根節(jié)點，得到的平均值為 1 / 1 = 1。 所以答案取最大值 6。提示： 樹中的節(jié)點數(shù)介于 1 到 5000之間。 每個節(jié)點的值介于 0 到 100000 之間。 如果結(jié)果與標(biāo)準(zhǔn)答案的誤差不超過 10^-5，那么該結(jié)果將被視為正確答案。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-average-subtree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

class Solution {double maxAVG = 0.0; public:double maximumAverageSubtree(TreeNode* root) {dfs(root);return maxAVG;}vector<int> dfs(TreeNode* root){if(!root) return {0, 0};//空節(jié)點的和 0，節(jié)點個數(shù)0auto l = dfs(root->left);//鉆到最底下去auto r = dfs(root->right);int n = 1+l[1]+r[1];//總節(jié)點個數(shù)int sum = root->val+l[0]+r[0];//子樹的和double avg = sum/double(n);if(avg > maxAVG)maxAVG = avg;return {sum, n};} };

40 ms 35.5 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1120. 子树的最大平均值（DFS自底向上）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。