【LeetCode 437】算法：路径总和 III
题目：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
核心思想：
这个问题的核心思想是深度优先搜索（DFS）结合递归。从二叉树的根节点开始，递归地遍历每个节点，并在遍历过程中计算从当前节点到任意叶子节点的路径和。如果路径和等于目标和 targetSum，则计数器加一。为了实现这一点，需要维护一个当前路径的和，并在遍历过程中更新它。
算法步骤：
[*]定义辅助函数：定义一个辅助函数 findPaths，它接受当前节点和目标和 targetSum 作为参数，用于计算以当前节点为起点，路径和为 targetSum 的路径数量。
[*]递归终止条件：如果当前节点为空，返回 0，因为没有路径。
[*]初始化计数器：对于每个节点，初始化计数器 count 为 0。
[*]检查叶子节点：如果当前节点是叶子节点（即没有左右子节点），检查当前节点的值是否等于 targetSum，如果是，则 count 加一。
[*]递归遍历子树：递归地调用 findPaths 函数遍历当前节点的左右子树，并将当前节点的值从 targetSum 中减去，因为路径和需要从当前节点开始计算。
[*]累加结果：在主函数 pathSum 中，递归地调用自身来遍历左子树和右子树，并将结果累加到 count 中。
[*]返回结果：返回 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;
}
}
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]