Re: [閒聊] 每日LeetCode已回收
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698900060.A.520.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 482 之 719 篇)：