题目

题目来源：力扣（LeetCode）

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

示例 1：
image.png

输入：root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

示例 2：
image.png

输入：root = [1,null,2,3,4,null,null,5,6]
输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）

示例 3：

输入：root = [2,3,9,10,7,8,6,5,4,11,1]
输出：1025

示例 4：

输入：root = [1,1]

思路分析

  • 首先，使用深度优先搜索计算出所有节点值之和 total，并求出中位数
  • 然后继续使用深度优先搜索，计算以每个节点为根节点的子树的所有节点之和 subSum，去掉一条边后的另一颗树的节点之和为 total-subSum，分裂二叉树的乘积为subSum * (total - subSum)
  • 枚举最大的乘积：当前拆分的子树越接近平均值，乘积越大
  • 注意：在计算分裂二叉树的乘积时，无需取模，否则会使大于等于mod的数变小，从而造成错误。
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. let avg = 0;
  14. let ans = 0;
  15. var maxProduct = function (root) {
  16.   // 计算所有节点值之和
  17.   let total = getTotal(root);
  18.   avg = total / 2;
  19.   ans = total;
  20.   // 计算以每个节点为根节点的子树的所有节点之和
  21.   getTotal(root);
  22.   // 计算乘积
  23.   return ans * (total - ans) % (10 ** 9 + 7)
  24. };
  25. var getTotal = function (root) {
  26.   if (root == null) return 0;
  27.   // 计算以每个节点为根节点的子树的所有节点之和
  28.   let val = root.val + getTotal(root.left) + getTotal(root.right);
  29.   // 当前拆分的子树越接近平均值，乘积越大
  30.   if (Math.abs(val - avg) < Math.abs(ans - avg)) ans = val;
  31.   return val;
  32. }