均匀树划分

/*
 * Problem Statement:
 * Given a binary tree, we need to determine if we can partition the tree into two subtrees with equal sum by removing exactly one edge.
 * The function `checkEqualTree` should return true if such a partition is possible, otherwise false.
 */
 
import java.util.stream.Stream;
import java.util.stream.Collectors;
import java.util.HashMap;
import java.util.Map;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public class EqualTreePartitionStream {
    // Helper method to calculate the sum of the entire tree
    private int sumTree(TreeNode root) {
        if (root == null) return 0;
        return Stream.of(root.val, sumTree(root.left), sumTree(root.right)).mapToInt(Integer::intValue).sum();
    }
 
    // Main method to check if we can partition the tree into two equal sum subtrees
    public boolean checkEqualTree(TreeNode root) {
        if (root == null) return false;
        int totalSum = sumTree(root);
        // If the total sum is odd, we cannot partition the tree
        if (totalSum % 2 != 0) return false;
        Map<TreeNode, Integer> subtreeSums = new HashMap<>();
        return canPartition(root, totalSum / 2, subtreeSums);
    }
 
    // Helper method to check if we can find a subtree with a given sum
    private boolean canPartition(TreeNode node, int target, Map<TreeNode, Integer> subtreeSums) {
        if (node == null) return false;
        int currentSum = Stream.of(node.val, canPartitionSum(node.left, target, subtreeSums), canPartitionSum(node.right, target, subtreeSums)).mapToInt(Integer::intValue).sum();
        subtreeSums.put(node, currentSum);
        if (currentSum == target) {
            subtreeSums.put(node, 0); // Reset the currentSum to prevent double counting
            return true;
        }
        return false;
    }
 
    // Helper method to calculate the sum of the subtree
    private int canPartitionSum(TreeNode node, int target, Map<TreeNode, Integer> subtreeSums) {
        if (node == null) return 0;
        return Stream.of(node.val, canPartitionSum(node.left, target, subtreeSums), canPartitionSum(node.right, target, subtreeSums)).mapToInt(Integer::intValue).sum();
    }
}