分裂二叉树的最大乘积 图解题解

这道题到底在问什么

输入

root=[50,30,80,10,40,60]

输出

18200(砍 80 上面那条边:140 × 130)

先想最直接的笨办法

记住「先求各子树和与 total,再枚举砍边算 sub ×(total − sub) 取最大,最后才取模」,下面逐帧套它。（动画第 3 步）

最优解：一步一步想明白

1. 3记住「先求各子树和与 total,再枚举砍边算 sub ×(total − sub) 取最大,最后才取模」,下面逐帧套它。
2. 4total = ?第一步:后序遍历,先算孩子、再算自己,求出每个节点的子树和。后序保证算到某个节点时,它的左右子树和都已就绪。
3. 5访问 50走到节点 50(紫色),先把它的孩子都算完,再回头算它自己的子树和。
4. 6访问 30走到节点 30(紫色),先把它的孩子都算完,再回头算它自己的子树和。
5. 7访问 10走到节点 10(紫色),它是叶子,子树里只有它自己。
6. 8子树和[10] = 10节点 10 的子树和 = 10 = 10(变绿,存进列表)。
7. 9访问 40走到节点 40(紫色),它是叶子,子树里只有它自己。
8. 10子树和[40] = 40节点 40 的子树和 = 40 = 40(变绿,存进列表)。
9. 11子树和[30] = 80节点 30 的子树和 = 30 + 10 + 40 = 80(变绿,存进列表)。
10. 12访问 80走到节点 80(紫色),先把它的孩子都算完,再回头算它自己的子树和。
11. 13访问 60走到节点 60(紫色),它是叶子,子树里只有它自己。
12. 14子树和[60] = 60节点 60 的子树和 = 60 = 60(变绿,存进列表)。
13. 15子树和[80] = 140节点 80 的子树和 = 80 + 60 = 140(变绿,存进列表)。
14. 16子树和[50] = 270节点 50 的子树和 = 50 + 80 + 140 = 270(变绿,存进列表)。它是根,这个和就是整棵树的总和 total。
15. 17total = 270所有子树和都算出来了,根的子树和 270 就是总和 total。接下来枚举每一棵子树:砍掉它上面那条边,看 sub ×(total − sub) 有多大。
16. 1810 × 260 = 2600砍掉节点 10 上面那条边:红色这棵子树和 = 10,蓝色剩下那半 = 270 − 10 = 260,乘积 = 2600。比之前大,刷新 best = 2600。
17. 1940 × 230 = 9200砍掉节点 40 上面那条边:红色这棵子树和 = 40,蓝色剩下那半 = 270 − 40 = 230,乘积 = 9200。比之前大,刷新 best = 9200。
18. 2080 × 190 = 15200砍掉节点 30 上面那条边:红色这棵子树和 = 80,蓝色剩下那半 = 270 − 80 = 190,乘积 = 15200。比之前大,刷新 best = 15200。
19. 2160 × 210 = 12600砍掉节点 60 上面那条边:红色这棵子树和 = 60,蓝色剩下那半 = 270 − 60 = 210,乘积 = 12600。没超过当前 best = 15200,保持不变。
20. 22140 × 130 = 18200砍掉节点 80 上面那条边:红色这棵子树和 = 140,蓝色剩下那半 = 270 − 140 = 130,乘积 = 18200。比之前大,刷新 best = 18200。
21. 23270 × 0 = 0代码里会把根的子树和 270 也算进去,但 270 ×(270 − 270)= 270 × 0 = 0,等于没切,自然不会被选为最大,可以放心一起遍历。
22. 24best = 18200所有砍法里,砍 80 上面那条边最优:把树分成和为 140 和 130 的两半,两者最接近一半,乘积最大 = 18200。
23. 25答案 = 18200最后一步才对最大乘积取模:18200 % (1e9+7) = 18200(本例数不大,取模后不变)。注意取模一定放在取完最大值之后,要是一边算乘积一边取模、再拿取模后的值比大小,就会比错。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        sums = []
        def dfs(node):
            if not node: return 0
            s = node.val + dfs(node.left) + dfs(node.right)
            sums.append(s)
            return s
        total = dfs(root)
        return max(s * (total - s) for s in sums) % (10**9 + 7)

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
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*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: int maxProduct(TreeNode* root){ vector<long long>sums; function<long long(TreeNode*)> dfs=[&](TreeNode*n){ if(!n)return 0LL; long long s=n->val+dfs(n->left)+dfs(n->right); sums.push_back(s); return s;}; long long total=dfs(root),best=0; for(long long s:sums)best=max(best,s*(total-s)); return best%1000000007; }};

import java.util.*;
class TreeNode{int val;TreeNode left,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{ ArrayList<Long>sums; public int maxProduct(TreeNode root){ sums=new ArrayList<>(); long total=dfs(root),best=0; for(long s:sums)best=Math.max(best,s*(total-s)); return (int)(best%1_000_000_007); } long dfs(TreeNode n){ if(n==null)return 0; long s=n.val+dfs(n.left)+dfs(n.right); sums.add(s); return s;} }

复杂度

面试官可能追问