1339. Maximum Product of Splitted Binary Tree

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree?envType=daily-question&envId=2026-01-07

今天的 daily 是 medium 的題目，感覺好久沒寫到 easy 了哈哈。

這個題目還蠻好理解的，看圖示還有描述應該很快就能明白意思了，但具體實作並不是那麼好想。

/**
 * 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:
    int MOD = 1000000007;
    int maxProduct(TreeNode* root) {
        long long right = 0, left = 0, total = 0;
        long long ans = 0;
        if(root->right) right = getSum(root->right);
        if(root->left) left = getSum(root->left);
        total = right + left + root->val;
        total = traverse(root, ans, total);

        return ans%MOD;
    }
    
    long long getSum(TreeNode* root) {
        long long left_sum = 0;
        long long right_sum = 0;
        if(root->left) left_sum = getSum(root->left);
        if(root->right) right_sum = getSum(root->right);

        return root->val+left_sum+right_sum;
    }

    long long traverse(TreeNode* root, long long& max_sum, long long& total_sum) {
        if(!root->left && !root->right) return root->val;
        long long right_sum = 0, left_sum = 0;
        if(root->right) {
            right_sum = traverse(root->right, max_sum, total_sum);
            max_sum = max(max_sum, right_sum*(total_sum-right_sum));
        }
        if(root->left) {
            left_sum = traverse(root->left, max_sum, total_sum);
            max_sum = max(max_sum, left_sum*(total_sum-left_sum));
        }

        return root->val + right_sum + left_sum;
    }
};

我用的演算法是 DFS，中間猶豫了一下要修改 data sructure 還是其他的方式，最後決定化繁為簡直接 DFS 硬寫。沒想到這樣在 performance beat 100%，memory 是只有 30%，有空再來看看別人的 memory 是怎麼省的！

Best Solution

TODO