LeetCode Entry
1339. Maximum Product of Splitted Binary Tree
fun maxProduct(root: TreeNode?): Int {
1339. Maximum Product of Splitted Binary Tree medium
https://t.me/leetcode_daily_unstoppable/47
fun maxProduct(root: TreeNode?): Int {
fun sumDfs(root: TreeNode?): Long {
return if (root == null) 0L
else with(root) { `val`.toLong() + sumDfs(left) + sumDfs(right) }
}
val total = sumDfs(root)
fun dfs(root: TreeNode?) : Pair<Long, Long> {
if (root == null) return Pair(0,0)
val left = dfs(root.left)
val right = dfs(root.right)
val sum = left.first + root.`val`.toLong() + right.first
val productLeft = left.first * (total - left.first)
val productRight = right.first * (total - right.first)
val prevProductMax = maxOf(right.second, left.second)
return sum to maxOf(productLeft, productRight, prevProductMax)
}
return (dfs(root).second % 1_000_000_007L).toInt()
}
Just iterate over all items and compute all products. We need to compute total sum before making the main traversal.
Space: O(logN), Time: O(N)