package leetcode;

/**
 * https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
 */
public class Problem1339 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int maxProduct(TreeNode root) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1339 prob = new Problem1339();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        System.out.println(prob.maxProduct(root)); // 110

        root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(6);
        System.out.println(prob.maxProduct(root)); // 90

        root = new TreeNode(1);
        root.left = new TreeNode(1);
        System.out.println(prob.maxProduct(root)); // 1
    }
}

@@ -340,32 +340,1362 @@
     
-// TODO
+SumTreeNode rootSumTreeNode = build(root);%0A        LongRef answer = new LongRef();%0A        maxProduct(rootSumTreeNode, rootSumTreeNode.sum, answer);%0A        return (int) answer.val;
 %0A    
+%7D%0A%0A
     
-return 0
+private static class SumTreeNode %7B%0A        private final long sum;%0A        private SumTreeNode left;%0A        private SumTreeNode right;%0A%0A        public SumTreeNode(int sum) %7B%0A            this.sum = sum;%0A        %7D%0A    %7D%0A%0A    private static class LongRef %7B%0A        private long val;%0A    %7D%0A%0A    private static void maxProduct(SumTreeNode root, long totalSum, LongRef max) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        long product = (root.sum * (totalSum - root.sum)) %25 1_000_000_007;%0A        max.val = Math.max(max.val, product);%0A        maxProduct(root.left, totalSum, max);%0A        maxProduct(root.right, totalSum, max);%0A    %7D%0A%0A    private static SumTreeNode build(TreeNode root) %7B%0A        if (root == null) %7B%0A            return null;%0A        %7D%0A        int sum = 0;%0A        SumTreeNode left = build(root.left);%0A        if (left != null) %7B%0A            sum += left.sum;%0A        %7D%0A        SumTreeNode right = build(root.right);%0A        if (right != null) %7B%0A            sum += right.sum;%0A        %7D%0A        SumTreeNode current = new SumTreeNode(sum + root.val);%0A        current.left = left;%0A        current.right = right;%0A        return current
 ;%0A  

Update problem 1339