本文主要是介绍[leetcode]2265. Count Nodes Equal to Average of Subtree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题入口
时间复杂度：O(n)，空间复杂度：O(h)
class Solution {
public:int count = 0;pair<int, int> postOder(TreeNode* root){if (!root)return {0, 0};pair<int, int> left = postOder(root->left);pair<int, int> right = postOder(root->right);int sum = left.first + right.first + root->val;int nodeCount = left.second + right.second + 1;int average = sum / nodeCount;if(average == root->val)count++;return {sum, nodeCount};}int averageOfSubtree(TreeNode* root) {postOder(root);return count;}
};时间复杂性：
-“postOrder”函数执行二进制树的后序遍历，访问每个节点一次。
-后序遍历的时间复杂度为O（n），其中n是树中的节点数。
空间复杂性：
-空间复杂度为O（h），其中h是二叉树的高度。
-这个空间用于后序遍历期间的递归调用堆栈。
在上面的方法中，我们必须多次迭代节点，因为我们是从上到下开始的，因此，我们无法重用总和和计数。我们可以用相反的方式迭代，而不是从根节点到叶子。我们将首先迭代每个节点的左子树和右子树，并返回节点的总和和节点的计数，然后我们可以找到平均值，并检查是否应该计算该节点。我们将对每个节点重复该过程，并在对所有节点进行迭代后返回最终计数。
时间复杂度：O(n^2), 空间复杂度：O(h)
class Solution {
public:int numsOfSubtree(TreeNode* root){if (!root)return 0;return numsOfSubtree(root->left) + numsOfSubtree(root->right) + 1;}int sumOfSubtree(TreeNode* root){if (!root)return 0;return sumOfSubtree(root->left) + sumOfSubtree(root->right) + root->val;}int averageOfSubtree(TreeNode* root) {if(!root)return 0;int average = sumOfSubtree(root) / numsOfSubtree(root);return ((root->val == average)? 1 : 0) + averageOfSubtree(root->left) + averageOfSubtree(root->right);}
};时间复杂性：
1. numsOfSubtree 和 sumOfSubtree 函数：这两个函数的时间复杂度为 (O(n)\)，其中 n 是树中的节点数。每个函数都会访问每个节点一次。
2. averageOfSubtree 函数：该函数对每个节点调用一次 `numsOfSubtree` 和 `sumOfSubtree`，并对每个节点递归调用自身。时间复杂度为 O(n^2)，因为对于每个节点，它计算了子树的总和和计数。
空间复杂性：
1. numsOfSubtree 和 sumOfSubtree 函数：这两个函数的空间复杂度为 O(h)，其中 h是树的高度。这是由于递归调用栈引起的。
2. averageOfSubtree 函数：由于递归调用栈，空间复杂度为 \(O(h)\)。
这篇关于[leetcode]2265. Count Nodes Equal to Average of Subtree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
