题解 | #牛群特殊路径的数量#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型
     */
    public int pathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return 0;
        }

        int pathsFromRoot = countPathsFromNode(root, sum, 0);
        int pathsFromLeft = pathSum(root.left,sum);
        int pathsFromRight = pathSum(root.right, sum);
        return pathsFromRoot + pathsFromLeft + pathsFromRight;
    }

    private static int countPathsFromNode(TreeNode node, int targetSum,
                                          int currentSum) {
        if (node == null) {
            return 0;
        }

        currentSum += node.val;
        int pathsCount = 0;

        if (currentSum == targetSum) {
            pathsCount++;
        }

        pathsCount += countPathsFromNode(node.left, targetSum, currentSum);
        pathsCount += countPathsFromNode(node.right, targetSum, currentSum);

        return pathsCount;
    }
}

知识点：

1. 基本的Java语法和概念。
2. 二叉树的遍历。
3. 递归算法的应用。

解题思路：

1. 从根节点开始，递归地向左子树和右子树搜索，计算以当前节点为起点的路径数目。
2. 对于每个节点，从当前节点出发，向下递归搜索路径，同时记录当前路径上的节点值之和。
3. 如果当前路径上的节点值之和等于目标值，增加路径计数。
4. 返回路径计数。

解释：

在这个实现中，我们首先从根节点开始递归地计算以当前节点为起点的路径数目。在递归过程中，我们记录当前路径上的节点值之和，如果等于目标值，则增加路径计数。然后，我们分别递归地计算左子树和右子树中满足条件的路径数目，并将它们累加起来。最终，我们可以得到总的路径数目。