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

Categories:

题目描述
思路分析
1. 解法一：两次 DFS 统计子树和（推荐）
相似题目

题目描述

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

思路分析

解法一：两次 DFS 统计子树和（推荐）

核心思路：

先 DFS 计算整棵树总和 total。

再 DFS 计算每个子树和 sub，更新 sub * (total - sub) 的最大值。

结果对 1e9+7 取模。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(h)，其中 h 表示树高。

class Solution {
    private static final int MOD = 1_000_000_007;
    private long total = 0;
    private long ans = 0;

    public int maxProduct(TreeNode root) {
        total = sum(root);
        dfs(root);
        return (int) (ans % MOD);
    }

    private long sum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + sum(node.left) + sum(node.right);
    }

    private long dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        long left = dfs(node.left);
        long right = dfs(node.right);
        long sub = node.val + left + right;

        // 更新最大乘积
        ans = Math.max(ans, sub * (total - sub));
        return sub;
    }
}

func maxProduct(root *TreeNode) int {
	const mod int64 = 1000000007
	total := sumTree(root)
	ans := int64(0)

	var dfs func(*TreeNode) int64
	dfs = func(node *TreeNode) int64 {
		if node == nil {
			return 0
		}
		left := dfs(node.Left)
		right := dfs(node.Right)
		sub := int64(node.Val) + left + right
		if sub*(total-sub) > ans {
			ans = sub * (total - sub)
		}
		return sub
	}

	dfs(root)
	return int(ans % mod)
}

func sumTree(node *TreeNode) int64 {
	if node == nil {
		return 0
	}
	return int64(node.Val) + sumTree(node.Left) + sumTree(node.Right)
}

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	DFS
124. 二叉树中的最大路径和	困难	DFS
1339. 分裂二叉树的最大乘积	中等	子树和
654. 最大二叉树	中等	递归
968. 监控二叉树	困难	树形 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/94370384