路径总和 III

原题链接

使用的方法

递归

解题思路

• 给定一个二叉树和一个整数目标值，我们需要找到路径总和等于目标值的路径数量。路径可以从树中的任何节点开始和结束，但必须沿着父子节点连接的方向。
• 我们可以使用递归来解决这个问题。
• 首先，我们定义一个全局变量 res 来记录路径总数。我们从根节点开始，调用一个辅助函数 dfs 来查找以当前节点为起点的路径总和等于目标值的路径数量。
• 在 dfs 函数中，我们首先检查当前节点是否为 null，如果是，则返回。然后，我们检查当前节点的值是否等于目标值，如果是，则将路径总数 res 加一。
• 接下来，我们继续递归地调用 dfs 函数来查找以当前节点的左子树和右子树为起点的路径总和等于目标值的路径数量。在递归调用时，我们将目标值减去当前节点的值，以便在后续的递归中正确计算路径总和。
• 最后，我们在主函数中继续递归地调用 pathSum 函数来查找以当前节点的左子树和右子树为起点的路径总和等于目标值的路径数量。这样，我们可以确保我们检查了树中的所有节点作为路径的起点。
• 最终，我们返回记录的路径总数 res 作为结果。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; // 记录路径总数
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) 
            return 0;
        
        dfs(root, targetSum); // 从当前根节点开始查找路径
        pathSum(root.left, targetSum); // 向左子树递归
        pathSum(root.right, targetSum); // 向右子树递归
    
        return res;
    }

    // 深度优先搜索遍历树
    public void dfs(TreeNode root, long targetSum) {
        if (root == null) 
            return;
        
        // 如果当前节点值等于目标值，计数加一
        if (root.val == targetSum) 
            res++;
        
        // 继续递归寻找更深的路径
        dfs(root.left, targetSum - root.val); // 左子树路径，回溯（减去当前节点值）
        dfs(root.right, targetSum - root.val); // 右子树路径，回溯（减去当前节点值）
    }
}