【LeetCode 437】算法：路径总和 III

题目：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

---

核心思想：

这个问题的核心思想是深度优先搜索（DFS）结合递归。从二叉树的根节点开始，递归地遍历每个节点，并在遍历过程中计算从当前节点到任意叶子节点的路径和。如果路径和等于目标和 targetSum，则计数器加一。为了实现这一点，需要维护一个当前路径的和，并在遍历过程中更新它。

算法步骤：

1. 定义辅助函数：定义一个辅助函数 findPaths，它接受当前节点和目标和 targetSum 作为参数，用于计算以当前节点为起点，路径和为 targetSum 的路径数量。
2. 递归终止条件：如果当前节点为空，返回 0，因为没有路径。
3. 初始化计数器：对于每个节点，初始化计数器 count 为 0。
4. 检查叶子节点：如果当前节点是叶子节点（即没有左右子节点），检查当前节点的值是否等于 targetSum，如果是，则 count 加一。
5. 递归遍历子树：递归地调用 findPaths 函数遍历当前节点的左右子树，并将当前节点的值从 targetSum 中减去，因为路径和需要从当前节点开始计算。
6. 累加结果：在主函数 pathSum 中，递归地调用自身来遍历左子树和右子树，并将结果累加到 count 中。
7. 返回结果：返回 count 作为最终结果。

复杂度分析：

时间复杂度：O(N)，其中 N 是二叉树中节点的数量。需要访问每个节点一次来计算路径和。

空间复杂度：O(H)，其中 H 是二叉树的高度。这是因为递归调用的深度最多为树的高度。

Java代码实现：

class Solution {int count = 0;public int pathSum(TreeNode root, int targetSum) {if (root == null) {return 0;}count += findPaths(root, targetSum);count += pathSum(root.left, targetSum);count += pathSum(root.right, targetSum);return count;}private int findPaths(TreeNode node, int targetSum) {if (node == null) {return 0;}int count = 0;if (node.val == targetSum) {count++;}if (node.left != null) {count += findPaths(node.left, targetSum - node.val);}if (node.right != null) {count += findPaths(node.right, targetSum - node.val);}return count;}
}