Medium

题目描述

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

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示：

  • 二叉树的节点个数的范围是 [0,1000]
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

解题思路

解题思路

这道题要求找出所有路径和等于目标值的路径数量，路径可以从任意节点开始，在任意节点结束，但必须向下。

方法一：双重递归（推荐）

核心思想是对每个节点都进行两种操作：

  1. 以当前节点为起点，向下寻找路径
  2. 递归处理左右子树

具体步骤：

  • pathSum 函数：遍历每个节点，对每个节点调用 dfs 函数
  • dfs 函数：从当前节点开始向下寻找所有满足条件的路径

方法二：前缀和优化

使用哈希表记录从根到当前节点的路径上所有前缀和的出现次数。对于当前节点，如果存在前缀和 currentSum - targetSum，说明存在以当前节点结尾且和为 targetSum 的路径。

时间复杂度从 O(N²) 优化到 O(N)。

这里提供双重递归解法，思路更直观易懂。

代码实现

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        
        // 以当前节点为起点的路径数 + 左子树的路径数 + 右子树的路径数
        return dfs(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
    
private:
    int dfs(TreeNode* node, long long targetSum) {
        if (!node) return 0;
        
        int count = 0;
        if (node->val == targetSum) count++;
        
        count += dfs(node->left, targetSum - node->val);
        count += dfs(node->right, targetSum - node->val);
        
        return count;
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root:
            return 0
        
        # 以当前节点为起点的路径数 + 左子树的路径数 + 右子树的路径数
        return self.dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)
    
    def dfs(self, node: Optional[TreeNode], targetSum: int) -> int:
        if not node:
            return 0
        
        count = 0
        if node.val == targetSum:
            count += 1
        
        count += self.dfs(node.left, targetSum - node.val)
        count += self.dfs(node.right, targetSum - node.val)
        
        return count

public class Solution {
    public int PathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // 以当前节点为起点的路径数 + 左子树的路径数 + 右子树的路径数
        return Dfs(root, targetSum) + PathSum(root.left, targetSum) + PathSum(root.right, targetSum);
    }
    
    private int Dfs(TreeNode node, long targetSum) {
        if (node == null) return 0;
        
        int count = 0;
        if (node.val == targetSum) count++;
        
        count += Dfs(node.left, targetSum - node.val);
        count += Dfs(node.right, targetSum - node.val);
        
        return count;
    }
}

var pathSum = function(root, targetSum) {
    if (!root) return 0;
    
    const prefixSumCount = new Map();
    prefixSumCount.set(0, 1);
    
    function dfs(node, currentSum) {
        if (!node) return 0;
        
        currentSum += node.val;
        let count = prefixSumCount.get(currentSum - targetSum) || 0;
        
        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
        
        count += dfs(node.left, currentSum);
        count += dfs(node.right, currentSum);
        
        prefixSumCount.set(currentSum, prefixSumCount.get(currentSum) - 1);
        
        return count;
    }
    
    return dfs(root, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双重递归解法
时间复杂度O(N²) - 最坏情况下每个节点都要遍历其子树
空间复杂度O(H) - H为树的高度，递归栈空间

相关题目