Detailed Dry Run of DFS on Trees!! 😸
Intuition\n\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nDFS \n\n# Complexity\
# Intuition\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS \n![Subtree avg.jpg](https://assets.leetcode.com/users/images/0ff0784f-9cae-4ac0-bdc0-69d028cd2346_1699673365.4682586.jpeg)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n        count = 0\n        def dfs(root):\n            nonlocal count\n            if not root:\n                return 0,0             \n            ls , lc = dfs(root.left)\n            rs , rc = dfs(root.right)\n            if root.val == (root.val + ls + rs) // (lc + rc + 1) : count += 1 \n            return root.val + ls + rs , lc + rc + 1\n        dfs(root)\n        return count\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python3']