2265. Count Nodes Equal to Average of Subtree
给你一个二元树
回传"所有结点等于该结点子树的平均值(无条件舍去)"的数量
直接举例比较清楚
https://assets.leetcode.com/uploads/2022/03/15/image-20220315203925-1.png
Input: root = [4,8,5,0,1,null,6]
Output: 5
对4来说 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4
对5来说 (5 + 6) / 2 = 11 / 2 = 5
对0来说 0 / 1 = 0
对1来说 1 / 1 = 1
对6来说 6 / 1 = 6
所以答案是5
Approach:
直接用递回找到子节点的总个数以及总和然后计算
做完这一题我去看别人的答案
才知道堆叠的空间复杂度也要算进去
TS code:
function averageOfSubtree (root: TreeNode | null): number {
let result = 0
const findIsAOS = (node: TreeNode | null): number[] => {
if (node === null) return [0, 0]
const [lSum, lCount] = findIsAOS(node?.left)
const [rSum, rCount] = findIsAOS(node?.right)
const sumACount = [lSum + rSum + node.val, lCount + rCount + 1]
if (Math.floor(sumACount[0] / sumACount[1]) === node.val) result++
return sumACount
}
findIsAOS(root)
return result
}