路径总和 IV

/*
 * Problem: Path Sum IV (LeetCode 666)
 * 
 * The task is to find the total sum of all the path sums from the root to the leaf nodes.
 * This solution uses Java Streams to create the tree and calculate the sum.
 */
 
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class PathSumIVStream {
    // Map to store the tree nodes with their depths and positions
    private Map<Integer, Integer> tree;
    // Variable to store the total path sum
    private int totalSum = 0;
 
    public int pathSum(int[] nums) {
        // Construct the tree map using streams
        tree = IntStream.of(nums).boxed().collect(Collectors.toMap(
            num -> (num / 100) * 10 + (num / 10) % 10,
            num -> num % 10
        ));
        // Start DFS traversal from the root node (depth 1, position 1)
        dfs(1, 1, 0);
        return totalSum;
    }
 
    private void dfs(int depth, int position, int currentSum) {
        // Key for the current node
        int key = depth * 10 + position;
        // If the node doesn't exist, return
        if (!tree.containsKey(key)) return;
 
        // Update the current path sum
        currentSum += tree.get(key);
 
        // Calculate the keys for left and right children
        int leftKey = (depth + 1) * 10 + (position * 2 - 1);
        int rightKey = (depth + 1) * 10 + (position * 2);
 
        // If the node is a leaf, add the current path sum to the total sum
        if (!tree.containsKey(leftKey) && !tree.containsKey(rightKey)) {
            totalSum += currentSum;
        } else {
            // Recursively visit left and right children
            dfs(depth + 1, position * 2 - 1, currentSum);
            dfs(depth + 1, position * 2, currentSum);
        }
    }
 
    public static void main(String[] args) {
        PathSumIVStream solution = new PathSumIVStream();
        int[] nums = {113, 215, 221};
        System.out.println(solution.pathSum(nums)); // Output should be the total path sum
    }
}