: 2265. Count Nodes Equal to Average of Subtree
: 給你一個二元樹
: 回傳"所有結點等於該結點子樹的平均值(無條件捨去)"的數量
: 直接舉例比較清楚
: https://assets.leetcode.com/uploads/2022/03/15/image-20220315203925-1.png
: Input: root = [4,8,5,0,1,null,6]
: Output: 5
: 對4來說 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4
: 對5來說 (5 + 6) / 2 = 11 / 2 = 5
: 對0來說 0 / 1 = 0
: 對1來說 1 / 1 = 1
: 對6來說 6 / 1 = 6
愚笨如我只想得到遞迴，不知道有沒有藏什麼數學特性
========== Python
from collections import defaultdict
class Solution:
def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
if (root == None):
return 0
self.subSum = defaultdict(int)
self.subCount = defaultdict(int)
self.count = 0
self.cal_avg(root)
return self.count
def cal_avg(self, node):
if (node == None):
return
elif (node.left == None and node.right == None):
self.subSum[node] = node.val
self.subCount[node] = 1
self.count += 1
else:
self.cal_avg(node.left)
self.cal_avg(node.right)
self.subSum[node] = node.val + self.subSum[node.left] +
self.subSum[node.right]
self.subCount[node] = self.subCount[node.left] +
self.subCount[node.right] + 1
if (node.val == (self.subSum[node] // self.subCount[node])):
self.count += 1
========== C++
class Solution {
private:
int count = 0;
unordered_map<TreeNode*, int> subSum;
unordered_map<TreeNode*, int> subCount;
public:
int averageOfSubtree(TreeNode* root) {
calAverage(root);
return count;
}
void calAverage(TreeNode* node)
{
if (node == nullptr) return ;
if (node->left == nullptr && node->right == nullptr)
{
subSum[node] = node->val;
subCount[node] = 1;
count++;
return;
}
else
{
calAverage(node->left);
calAverage(node->right);
subSum[node] = node->val + subSum[node->right] +
subSum[node->left];
subCount[node] = 1 + subCount[node->right] + subCount[node->left];
if (node->val == (subSum[node] / subCount[node])) count++;
}
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.209.225 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698953585.A.12D.html