Two Solutions | Brute➡️Optimal - DFS | ✅Clean & Simple CPP Code✅
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣IntuitionHello There Its Easy! Take A Look At The Code And Comments Within It You'll Get It.
Still Have Doubts! Feel Free To Comment, I'll D
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
***Hello There Its Easy! Take A Look At The Code And Comments Within It You'll Get It.
Still Have Doubts! Feel Free To Comment, I'll Definitely Reply!***

# Approach
<!-- Describe your approach to solving the problem. -->
***All Accepted :
-> Using DFS (Brute Force)
-> Using DFS (Time Optimized)***

***Note: I'll add comments soon!***

# Complexity
- ***Time complexity: Mentioned with the code***
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity: Mentioned with the code***
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
**Approach 1 : Using DFS (Brute Force)**
```
class BruteDFS {
    int result = 0;

    void getSumAndCount(TreeNode* rootNode, int& subtreeSum, int& totalNodes) {
        if(rootNode) {
            totalNodes++;
            subtreeSum += rootNode->val;
            getSumAndCount(rootNode->left, subtreeSum, totalNodes);
            getSumAndCount(rootNode->right, subtreeSum, totalNodes);
        }
    }

public:
    // O(N*N) & O(H)
    int averageOfSubtree(TreeNode* rootNode) {
        if(!rootNode)
            return 0;

        int subtreeSum = 0, totalNodes = 0;
        getSumAndCount(rootNode, subtreeSum, totalNodes);

        result += (subtreeSum / totalNodes == rootNode->val);

        averageOfSubtree(rootNode->left);
        averageOfSubtree(rootNode->right);

        return result;
    }
};
```
**Approach 2 : Using DFS (Time Optimized)**
```
class BottomUpDFS {
public:
    // O(N) & O(H)
    int averageOfSubtree(TreeNode* rootNode) {
        int result = 0;
        calcAvgAndUpdateResult(rootNode, result);
        return result;
    }

private:
    std::pair<int, int> calcAvgAndUpdateResult(TreeNode* rootNode, int& result) {
        if(!rootNode)
            return {0, 0};

        auto [sumLeftSubtree,  nodesLeft]  = calcAvgAndUpdateResult(rootNode->left, result); 
        auto [sumRightSubtree, nodesRight] = calcAvgAndUpdateResult(rootNode->right, result); 

        int sumCurrSubtree = sumLeftSubtree + sumRightSubtree + rootNode->val; 
        int totalNodes = nodesLeft + nodesRight + 1;

        result += (sumCurrSubtree / totalNodes == rootNode->val);

        return {sumCurrSubtree, totalNodes};
    }
};
```
𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']