[力扣每日习题][1339]. 分裂二叉树的最大乘积 2026.01.07

难度评级：中等

题目：

给你一棵二叉树，它的根为 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）

解题思路：DFS

        可以先计算得到所有节点的和，再通过数组存储所有子树的和，遍历数组的时候，计算：子树和  × （所有节点和 - 子树和），也就是分割成两个子树的乘积，找出最大的那一个乘积即可。

        深度优先搜索就是沿着一条路走到底，走不通了再回到上一层继续走。可以采用递归的方式实现，将根节点作为起始节点放入函数当中，函数需要完成如下操作：

        ① 定义 left 、 right、temp 3个参数，每次调用 DFS 函数的时候都需要重置为 0 ；

        ② 判断是否有左孩子，有就调用 DFS 函数，并且将函数的返回值存入 left 中，没有就下一步；

        ③ 判断是否有右孩子，有就调用 DFS 函数，并且将函数的返回值存入 right 中，没有就下一步；

        ④ 计算 temp = left + right + 当前节点的值；

        ⑤ 将 temp 存入子树和的数组中。

        ⑥ 返回 temp（当前子树的和）；

        解析：根节点调用 DFS 函数的时候，会一直嵌套直到找到二叉树最左边的那个叶子节点，接下来，由于 left 和 right 为 0，那么 temp = 0 + 0 + 当前节点的值，将 temp 返回至上一层，也就是当前节点的父亲节点，父亲节点已经完成了 ② ，在这一层 left 的值是刚才计算得到的 temp，接下来进行 ③ ，如果没有右孩子那么 right = 0，在这一层的 temp = left + 0 + 当前节点的值，结束这层循环，再返回上一层。

        理解 DFS 的关键就是，先找到一条路一直到底，然后再慢慢往回退。

        接下来我们用一颗二叉树来模拟一下这个 DFS 的流程。

        以如下二叉树为例，依次分析每个节点，下面是根节点的初始状态，将各个参数重置为 0，temp是当前节点孩子子树的和＋当前节点值；注意这里的 left 和 right 分别指的左孩子子树的和、右孩子子树的和，不是左孩子和右孩子的值，在代码中为 left = DFS（2）；right = DFS（3）；是递归调用函数后返回的值。

        对于 1 这个节点，它有左孩子，那么这里需要递归调用 DFS 函数，将 2 这个节点作为根节点进行分析，对应着步骤 ②，2 这个节点进入后，它需要开始循环它的 DFS 函数。

        节点 2 有左孩子 4，那么将节点 4 作为根节点进行分析，调用 DFS 函数。

        此时节点 4 ，进行步骤 ②、③，由于它没有孩子，那么只能进行步骤 ④，计算 temp，最后将计算结果保存。

        第三层 4 进行步骤 ⑥，返回上一层，将计算结果返回给上一层对应调用 DFS（4）的那个参数，上一层调用 DFS（4）的是 第二层 2 在步骤 ② 的时候将左孩子进行递归调用 DFS，那么值就返回给第二层 2 的参数 left。

        第二层 2 的步骤 ② 结束，现在进行步骤 ③ ，它有右孩子，那么将节点 5 调用 DFS 函数，作为根节点进行分析。

        节点 5，没有左右孩子，直接进行步骤 ④。

        进行步骤 ⑥，将值返回给上一层的 right。

        现在第三层 5 结束，第二层 2 进行步骤 ④，计算它自己的 temp。

        第二层 2 ，进行步骤 ⑥，将值返回给上一层的 left。

        第二层 2 结束，现在对一层 1 进行步骤 ③，它有右孩子，将右孩子递归调用 DFS

        节点 3 ，它没有左孩子，只有右孩子，那么它直接进行步骤 ③。

        第三层 6 ，没有孩子，是叶子节点，直接步骤 ④，计算 temp。

        进行步骤 ⑥，返回上一层，将值给上一层的 right。

        第二层 3 进行步骤 ④。

        进行步骤 ⑥，返回上一层，将值返回给上一层的 right。

        第一层 1 进行步骤 ④。

        最后进行步骤 ⑥，将最后的值返回即可，在递归调用的时候，所有的子树和都已计算并保存至一个数组，接下来只需要遍历数组，计算 每棵子树和  * （总和 - 该子树和） 找到最大值就可以了。

题解代码如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: const int MOD = 1e9 + 7; long long dfs(TreeNode* root, vector<long long>& list){ long long l = 0; long long r = 0; long long temp = 0; if (root -> left != nullptr){ l = dfs(root -> left, list); } if (root -> right != nullptr){ r = dfs(root -> right, list); } temp = l + r + root -> val; list.push_back(temp); return temp; } int maxProduct(TreeNode* root) { vector <long long> list; // 用于存储所有子树和 long long sum = dfs(root, list); long long res = 0; for (auto i:list){ long long cal = i * (sum - i); if (cal > res){ res = cal; } } return res % MOD; } };

优化思路：暂无。