路径总和 III

/* 
思路：
1. 将树的节点转换为列表。
2. 使用流操作计算路径和。
3. 通过递归计算每个节点的路径和。
4. 使用流操作求和。 
*/

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        List<TreeNode> nodes = new ArrayList<>();
        traverse(root, nodes);
        return nodes.stream().mapToInt(node -> countPaths(node, targetSum)).sum();
    }

    private void traverse(TreeNode node, List<TreeNode> nodes) {
        if (node != null) {
            nodes.add(node);
            traverse(node.left, nodes);
            traverse(node.right, nodes);
        }
    }

    private int countPaths(TreeNode node, int sum) {
        if (node == null) return 0;
        return (node.val == sum ? 1 : 0) 
            + countPaths(node.left, sum - node.val) 
            + countPaths(node.right, sum - node.val);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}