1339. Maximum Product of Splitted Binary Tree

解题思路：根据题目描述，找出删除一条边之后两棵二叉树的最大乘积。两棵二叉树的最大乘积应该是差值最小的两棵树，所以解题需要知道以每一个节点为根的二叉树的和，所以解题主要分三步：

• 更新树节点为以此节点为根的二叉树的节点和
• 找出差值最小的两棵二叉树的和
• 返回答案

时间复杂度：O(n) / 空间复杂度：O(1)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNode(TreeNode* node){
        if(node == nullptr){
            return 0;
        }
        node->val += sumNode(node->left) + sumNode(node->right);
        return node->val;
    }
    void traverse(TreeNode* node, int& num, int& curDiff, int sum){
        if(node == nullptr){
            return;
        }
        if(abs(node->val - (sum - node->val)) < curDiff){
            curDiff = abs(node->val - (sum - node->val));
            num = node->val;
        }
        traverse(node->left, num, curDiff, sum);
        traverse(node->right, num, curDiff, sum);
        return;
    }
    int maxProduct(TreeNode* root) {
        int treeSum = sumNode(root);
        int curDiff = INT_MAX;
        int num = 0;
        traverse(root, num, curDiff, treeSum);
        // std::cout << "num: " << num << std::endl;
        return ((long)num * (long)(treeSum - num)) % 1000000007;
    }
};