A.每日一题——1339. 分裂二叉树的最大乘积

题目链接：1339. 分裂二叉树的最大乘积（中等）

算法原理：

解法：两次DFS

8ms击败80.19%

时间复杂度O(n)

第一次dfs：计算整棵树的元素总和total

第二次dfs：计算子树的元素总和t，分割的另外一棵子树的元素和乘积可表示为 total-t

在遍历子树的同时统计乘积 t*(total-t) 的最大值，先用long类型存下，最后返回的时候再取模转化为int

Java代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private static final int MOD=1_000_000_007; private long ret=0; private int total; public int maxProduct(TreeNode root) { total=dfs1(root); dfs2(root); return (int)(ret%MOD); } private int dfs1(TreeNode node){ if(node==null) return 0; return node.val+dfs1(node.left)+dfs1(node.right); } private int dfs2(TreeNode node){ if(node==null) return 0; int t=node.val+dfs2(node.left)+dfs2(node.right); ret=Math.max(ret,(long)t*(total-t)); return t; } }