[leetcode]2265. Count Nodes Equal to Average of Subtree
2023-12-13 22:13:30
问题入口
时间复杂度: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)。
文章来源:https://blog.csdn.net/qq_37120435/article/details/134828451
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!