当前位置：网站首页>[binary tree] maximum product of split binary tree

[binary tree] maximum product of split binary tree

2022-07-21 15:10:00 【How cold it is】

0x00 subject

Here is a binary tree for you , Its root is root
Please delete 1 side , Split the binary tree into two subtree
And their subtrees and Of The product of As big as possible

Because the answer could be big
Please put the result to 10^9 + 7 Take the mold and return to

0x01 Ideas

Because the tree should be divided into 2 part
Suppose the sum of the first tree after segmentation is S
Then the sum of the remaining parts is the sum of the whole subtract S
So we need to find the sum of the whole tree first T
Because I don't know which node is the root of the first tree
So any node needs Traverse To
bring S * (T - S) Maximum
Simultaneous recording Maximum value

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func maxProduct(_ root: TreeNode?) -> Int {
    //  result 
    var res: Int = Int.min
    //  The sum of the 
    var allSum: Int = 0
    //  Part I molecular tree and 
    var nodeSum: Int = 0
    
    //  Sum up 
    func sum(_ root: TreeNode?) -> Int {
        guard let r = root else { return 0 }
        return r.val + sum(r.left) + sum(r.right)
    }
    
    //  Recursively find subtrees and 
    func dfs(_ root: TreeNode?) -> Int {
        guard let r = root else { return 0 }
        
        //  Subtree and 
        nodeSum = r.val + dfs(r.left) + dfs(r.right)
        
        //  Calculate the maximum 
        res = max(res, (allSum - nodeSum) * nodeSum)
        return nodeSum
    }
    
    allSum = sum(root)
    _ = dfs(root)
    res = res % (Int(1e9) + 7)
    
    return res
}