1339. 分裂二叉树的最大乘积 - Kotlin 动态规划 线段树思想

Problem: 1339. 分裂二叉树的最大乘积

思路

题意可以理解为：将整个二叉树从任意一个节点（除根节点）摘下，使该节点成为一个新的根，从而将整个二叉树拆分为两颗子树。我们需要找到一个节点，从这个节点摘下后两棵子树的和的乘积最大。

我们可以参照线段树的思想，将二叉树的节点值修改为以该节点为根节点时，其子树的和，理所当然的，整颗二叉树的根节点的值应当为全部节点的和。由于要先计算左子树的和和右子树的和，才能计算该节点的值，因此应当采用后序遍历的方法遍历树

随后我们以任意方式遍历二叉树，由于我们已经知道了整个二叉树的和为根节点的值，对于任何一颗子树a，将其拆分下来后另一颗子树b的和应当为，即得到的乘积为

对所有乘积取最大值即为结果

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution {
    fun TreeNode.presum() {
        this.left?.presum()
        this.right?.presum()
        this.`val` += (left?.`val` ?: 0) + (right?.`val` ?: 0)
    }

    fun TreeNode.search(rootVal: Int): Long {
        val leftVal = this.left?.search(rootVal)
        val rightVal = this.right?.search(rootVal)
        val thisVal: Long = (this.`val`).toLong() * (rootVal - this.`val`).toLong()
        return longArrayOf(leftVal ?: 0, rightVal ?: 0, thisVal).max()!!
    }

    fun maxProduct(root: TreeNode?): Int {
        root?.presum()
        return ((root?.search(root.`val`) ?: 0) % 1000000007).toInt()
    }
}