宝宝也能看懂的 leetcode 周赛 - 174 - 3

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

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 174 期的第 3 题,也是题目列表中的第 1339 题 -- 『分裂二叉树的最大乘积』

题目描述

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

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

示例 1:

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

示例 2:

输入: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]
输出:1

提示:

  • 每棵树最多有 50000个节点,且至少有 2个节点。
  • 每个节点的值在 [1, 10000]之间。

官方难度

MEDIUM

解决思路

题目提供了一棵二叉树的根节点,需要我们删除一条边使得这棵二叉树变成两棵二叉树。而要求就是对这两棵二叉树里各个节点分别求和之后,这两个和的乘积最小。

不知道小伙伴们是什么想法,不过小猪看完题目之后第一反应是,先遍历起来。毕竟,只对着一个根节点的话,再好的戏也出不来。而提到遍历二叉树的话,又想少写一点代码,那小猪的第一反应就是用递归来实现深度优先遍历啦。

接下来回到题目的需求上,我们需要找到拆分后两个和的乘积最大。由于这棵树给定后就不会变了,所以所有节点求和的值其实是一定的。而对于这个确定的值,我们把它拆成两个加数后要使得它们的乘积最大,那么这两个数应该尽可能的靠近总和的二分之一。相信到这里,很多小伙伴都是能想到哒。不过再往后,如果直接用数学的方式来处理这个问题,小猪就想不明白了。小猪苯苯的,希望小伙们能帮帮我。

那没有了数学的方法,小猪就只能用计算机的方法啦。我们可以想象一下,在去掉一条边之后,拆分成的两棵二叉树,其中必然有一棵的顶点位于我们刚才断掉的那条边的下游。也就是说,从当前位置拆开之后,其实分成的两部分,就是以当前节点为顶点的二叉树,以及其他的节点。

想通了这一点之后,再结合前面提到的总和是固定不变的。那么我们的思路也就大概清晰啦。

直接方案

我们可以先计算出所有节点的总和。然后对于每一个节点,我们也能算出以它为顶点的子二叉树的总和。那么剩下的那一部分也就知道啦。在对每个可能的节点都进行这样的计算之后,我们就能找到那个最大的乘积了。

基于这个思路,我们具体的流程如下:

  1. 遍历二叉树,得到所有节点值的总和。
  2. 遍历二叉树,针对每一个可能的节点,假设从这里拆分,然后计算可能的乘积,并记录最大值。
  3. 返回最大的乘积。

基于这个流程,我们可以实现类似下面的代码:

const maxProduct = root => {
  let sum = max = 0;
  sum = helper(root);
  helper(root);
  return max % (10 ** 9 + 7);

  function helper(node) {
    const subSum = node.val + (node.left ? helper(node.left) : 0) + (node.right ? helper(node.right) : 0);
    sum && subSum * (sum - subSum) > max && (max = subSum * (sum - subSum));
    return subSum;
  }
};

优化

上面的代码我们对整个二叉树进行了两次遍历,其中第一次是为了计算总和,而第二次则是进行每个节点的子二叉树的计算和判断。

不知道小伙伴们有没有发现,其实我们第二次遍历中所计算的东西,在第一次遍历的时候也是可以得到的。而唯一最初无法计算的,就是与总和的差值做乘积的结果。那么我们其实可以把前面的内容都记录下来,在得到了总和之后直接进行计算即可。

基于这个优化思路,我们具体的流程如下:

  1. 遍历二叉树,得到所有节点值的总和,并记录以每个节点为首的子二叉树的总和。
  2. 尝试这些子二叉树的和,并计算出最大的乘积。

基于这个流程,我们可以实现类似下面的代码:

const maxProduct = root => {
  const subSums = new Uint32Array(50000);
  let max = idx = 0;
  const sum = helper(root);
  for (let i = 0; i < idx; ++i) {
    const val = subSums[i];
    val * (sum - val) > max && (max = val * (sum - val));
  }
  return max % (10 ** 9 + 7);

  function helper(node) {
    const subSum = node.val + (node.left ? helper(node.left) : 0) + (node.right ? helper(node.right) : 0);
    subSums[idx++] = subSum;
    return subSum;
  }
};

总结

这道题的逻辑并不复杂,还是非常套路的内容。关键点就是在与要相通我们拆分后的情况究竟是什么,也就是分析中提到的拆分之后其中一部分必然是以当前节点为首的子二叉树。而剩下的就是套用深度优先遍历去实现即可。

在我们这么多期的周赛题解之后,相信小伙伴们已经逐渐的开始熟悉这些套路了吧。突然觉得小猪做的事情还是有意义的呢,开心的摇了摇猪尾巴 >.<

相关链接

原文链接:segmentfault.com

上一篇:@hypha/web-compiler
下一篇:node+multer实现图片上传

相关推荐

  • 茄子算法每日N题之LeetCode面试题22. 链表中倒数第k个节点

    LeetCode 面试题22. 链表中倒数第k个节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode面试题22. 链表中倒数第k个节点 输入一个链表,输出该链表...

    21 天前
  • 茄子算法每日N题之LeetCode面试题 02.01. 移除重复节点

    LeetCode 面试题 02.01. 移除重复节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode面试题 02.01. 移除重复节点 编写代码,移除未排序链表...

    20 天前
  • 茄子算法每日N题之LeetCode876链表的中间结点

    LeetCode 876.链表的中间结点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

    1 个月前
  • 茄子算法每日N题之LeetCode86. 分隔链表

    LeetCode 86. 分隔链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode86.分隔链表 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x...

    22 天前
  • 茄子算法每日N题之LeetCode83删除排序链表中的重复元素

    LeetCode 83.删除排序链表中的重复元素|| 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode83删除排序链表中的重复元素 给定一个排序链表,删除所有重复...

    1 个月前
  • 茄子算法每日N题之LeetCode45跳跃游戏 II

    LeetCode 45.跳跃游戏 II 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode45.跳跃游戏 II(每日一题/5月4日) 给定一个非负整数数组,你最初位...

    1 个月前
  • 茄子算法每日N题之LeetCode25K个一组翻转链表

    LeetCode 25.K个一组翻转链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    1 个月前
  • 茄子算法每日N题之LeetCode24两两交换链表中的节点

    LeetCode 24.两两交换链表中的节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

    1 个月前
  • 茄子算法每日N题之LeetCode23.合并K个排序链表

    LeetCode 23.合并K个排序链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 23.合并K个排序链表 合并 k 个排序链表,返回合并后的排序链表。

    23 天前
  • 茄子算法每日N题之LeetCode207移除链表元素

    LeetCode 207.移除链表元素 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1&gt;2&gt;6&gt;...

    1 个月前

官方社区

扫码加入 JavaScript 社区