【二叉树-中等】2265. 统计值等于子树平均值的节点数

【题目】
【代码】
【方法1】
使用先序遍历+哈希，占用较高的额外空间

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def visit(self,root):
        if not root:
            return 
        if root.val not in self.cnt:
            self.cnt[root]=[]
        if root.left:
            self.cnt[root].append(root.left)
        if root.right:
            self.cnt[root].append(root.right)
        self.visit(root.left)
        self.visit(root.right)

    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        self.cnt={
    }
        ans=0
        self.visit(root)
        # print(self.cnt)
        for key in self.cnt:     
            temp_list=self.cnt[key]
            for item in temp_list:                
                if item in self.cnt:
                    temp_list+=self.cnt[item]
            temp_list=[item.val for item in temp_list]
            temp_sum=0
            if len(temp_list):
                temp_sum=sum(temp_list)
            temp_sum+=key.val
            if key.val==(temp_sum//(1+len(temp_list))):
                ans+=1
        return ans

【方法2】
使用后序遍历

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        # 统计每个子树的总值和个数
        ans = 0
        def dfs(root):
            nonlocal ans
            if root is None:
                return 0,0
            l,countLeft = dfs(root.left)
            r,countRight = dfs(root.right)
            if root.val == (root.val+l+r)//(countRight+countLeft+1):
                ans += 1
            return root.val+l+r ,countRight+countLeft+1
        dfs(root)
        return ans