发表于 2024.07.31

• 分析可知，切分后的两个子树的和越接近，乘积就越大。此外，其中一棵子树就是原树中以某个节点为根的子树，另外一棵则是以原树的根节点为根的、剩余节点构成的树。因此，只需要求出所有子树的和，然后找到和最接近总和一半的子树即可。

  官解使用的是二次遍历的方法，首先第一次用于求和，然后第二次再找到最大的乘积。这里使用后序遍历的方法，一次遍历得到所有子树的和，然后再找到最接近总和一半的子树即可。

  class Solution:
      MOD = 10 ** 9 + 7
  
      def maxProduct(self, root: Optional[TreeNode]) -> int:
          tree_sums = []  # 保存所有子树的和
  
          def inorder(node: Optional[TreeNode]):
              if node is None:
                  return 0
              tree_sum = inorder(node.left) + inorder(node.right) + node.val
              tree_sums.append(tree_sum)
              return tree_sum
  
          inorder(root)
          all_sum = tree_sums[-1]  # 总和在最后一个元素(因为是后序遍历)
          half = all_sum // 2  # 总和的一半
          target = all_sum
          for root_val in tree_sums:
              if abs(target - half) > abs(root_val - half):  # 找到一个和更接近总和一半的子树
                  target = root_val
          return (target * (all_sum - target)) % self.MOD

  C++的做法：

  class Solution {
  public:
      using ll = long long;
      vector<int> tree_sum_list;
  
      ll inorder(TreeNode* node) {
          if (node == nullptr) return 0;
          ll sum = node->val + inorder(node->left) + inorder(node->right);
          tree_sum_list.push_back(sum);
          return sum;
      }
  
      int maxProduct(TreeNode* root) {
          auto all_sum = inorder(root);
          auto cand = all_sum;
          auto half = all_sum / 2;
          for (auto &tree_sum : tree_sum_list) {
              if (abs(tree_sum - half) < abs(cand - half)) cand =  tree_sum;
          }
          return cand * (all_sum - cand) % 1000000007;
      }
  };
      

• LC 题目链接