[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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。