🌳 初学者友好指南 “Maximum Product of Splitted Binary Tree” – LeetCode 1339 (C++, Python, JavaScript)

Source: Dev.to

二叉树常常因为其递归特性而让人感到畏惧。然而，许多树问题只需观察单个节点与其余结构的关系即可解决。在本指南中，我们将学习如何 “剪断”一条边以最大化数学乘积。

Problem Statement

您得到：

• 一个二叉树的根节点，每个节点包含一个整数值。

您的目标：

1. 通过删除恰好一条边，将树拆分为两个独立的子树。
2. 计算两个结果树中节点的和。
3. 最大化这两个和的乘积，并返回结果 模 (10^9 + 7)。

直觉

问题要求我们找到两个数字（两个子树的和），使它们的乘积尽可能大。
如果我们知道树中所有节点的总和，记为 (S)，并且我们找到任意子树的和，记为 (x)，那么树剩余部分的和必须是 (S - x)。

为了获得最大乘积，我们需要：

1. 计算总和 – 遍历整棵树一次以计算 (S)。
2. 评估每一种可能的划分 – 每条边连接父节点和一个子树。切断该边会得到子树的和 (x)。
3. 计算乘积 – 对每个子树和计算 (x \times (S - x))。
4. 跟踪最大值 – 在遍历过程中保持看到的最大乘积。

后序遍历（左、右、节点）在这里非常合适，因为它让节点在计算自身总和之前先知道其子节点的和。

代码

C++

class Solution {
public:
    const long long MOD = 1e9 + 7;
    long long total = 0;   // total sum of all nodes
    long long ans   = 0;   // best product found

    // First pass – compute total sum
    void calculateTotal(TreeNode* root) {
        if (!root) return;
        total += root->val;
        calculateTotal(root->left);
        calculateTotal(root->right);
    }

    // Second pass – post‑order, compute subtree sums and update answer
    long long subTreeSum(TreeNode* root) {
        if (!root) return 0;

        long long leftSum  = subTreeSum(root->left);
        long long rightSum = subTreeSum(root->right);

        // If we cut the edge to the left child
        ans = max(ans, leftSum * (total - leftSum));
        // If we cut the edge to the right child
        ans = max(ans, rightSum * (total - rightSum));

        return leftSum + rightSum + root->val;
    }

    int maxProduct(TreeNode* root) {
        calculateTotal(root);      // O(N)
        subTreeSum(root);          // O(N)
        return ans % MOD;
    }
};

Python

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.total = 0          # total sum of all nodes
        self.ans   = 0          # best product found

        # First pass – compute total sum
        def get_total(node):
            if not node:
                return
            self.total += node.val
            get_total(node.left)
            get_total(node.right)

        # Second pass – post‑order, compute subtree sums and update answer
        def get_subtree_sum(node):
            if not node:
                return 0

            left_sum  = get_subtree_sum(node.left)
            right_sum = get_subtree_sum(node.right)

            cur_sum = left_sum + right_sum + node.val
            # Update max product (do NOT mod yet)
            self.ans = max(self.ans, cur_sum * (self.total - cur_sum))
            return cur_sum

        get_total(root)          # O(N)
        get_subtree_sum(root)    # O(N)

        return self.ans % (10**9 + 7)

JavaScript

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function (root) {
    let total = 0;   // total sum of all nodes
    let ans   = 0;   // best product found

    // First pass – compute total sum
    const getTotal = (node) => {
        if (!node) return;
        total += node.val;
        getTotal(node.left);
        getTotal(node.right);
    };

    // Second pass – post‑order, compute subtree sums and update answer
    const getSubtreeSum = (node) => {
        if (!node) return 0;

        const leftSum  = getSubtreeSum(node.left);
        const rightSum = getSubtreeSum(node.right);
        const curSum   = leftSum + rightSum + node.val;

        const product = curSum * (total - curSum);
        if (product > ans) ans = product;

        return curSum;
    };

    getTotal(root);          // O(N)
    getSubtreeSum(root);     // O(N)

    // Use BigInt for safety before applying modulo
    return Number(BigInt(ans) % 1000000007n);
};

---

关键要点

• 后序遍历 在节点的计算依赖于其子节点时非常理想（这里我们需要子树的和）。
• 两遍策略 常常简化问题：首先收集全局信息（总和），然后执行核心逻辑（乘积计算）。
• 先求最大再取模 —— 过早取模会改变乘积的排序，导致答案错误。

最终思考

作为导师，我经常看到学生在树形问题上苦苦挣扎，因为他们试图一次性想象所有可能的划分。相反，应该关注这样一个属性：切断任意一条边会隔离出整个子树。通过将问题简化为“每个子树的和是多少？”，并使用一次简单的后序遍历，解法既直观又高效。祝编码愉快！ 🚀

树中的递归求和

单个节点：
“如果我知道我下面所有节点的总和，我就能确定整棵树其余部分的总和。”

这种逻辑是 网络路由算法 的基础，工程师必须确定最佳的流量分割点或识别 瓶颈 节点。它在数据科学中的 层次聚类 中也非常相关。

掌握这些递归模式将使你成为更高效的软件工程师。