路径总和Ⅲ（前缀和法）

题解思路

这道题目要求我们计算二叉树中所有路径和等于给定目标值 targetSum 的路径数量。可以利用 前缀和 的思路来优化算法。

关键点分析

1. 路径的定义：路径不一定从根节点开始，也不一定在叶子节点结束，路径必须是从父节点到子节点进行传递。
2. 前缀和的思路：前缀和是一种在数组或树中计算区间和的技巧，可以通过记录路径的前缀和来减少冗余计算，避免重复遍历子树。

前缀和的应用

我们可以通过在遍历树的过程中维护当前路径的前缀和，并使用哈希表记录每个前缀和出现的次数。具体的思想是：

1. 在递归过程中，每当访问一个节点时，计算从当前节点到根节点的路径和（前缀和）。
2. 如果当前前缀和减去目标值 targetSum 结果在哈希表中出现过，说明有路径和等于 targetSum，因为从某个先前的节点到当前节点的路径和就是 targetSum。
3. 通过维护前缀和的哈希表，可以高效地统计满足条件的路径数。

解题步骤

1. 前缀和的哈希表：使用哈希表 prefixSum 来记录每个前缀和出现的次数，初始时 prefixSum[0] = 1，表示从根节点开始就有一个路径和为 0。
2. 深度优先搜索（DFS）：通过递归方式遍历树的每个节点，在递归过程中维护当前路径的前缀和。每访问一个节点，就更新前缀和，并检查是否存在某个前缀和为 current_sum - targetSum。
3. 路径计数：每当发现某个路径的和等于目标值时，就更新结果计数。

算法步骤

1. 从根节点开始，递归地遍历每个节点。
2. 对每个节点，计算从该节点到根节点的路径的前缀和。
3. 使用哈希表记录出现过的前缀和，每次计算当前路径的前缀和时，检查 prefixSum[current_sum - targetSum] 是否存在，若存在，则路径和等于目标值，计数加一。
4. 递归地访问左右子树，并更新前缀和。

代码实现

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(level_order):
    # 将层次遍历结果构建成二叉树
    if not level_order or level_order[0] == 'null':
        return None
    
    nodes = []
    index = 0
    root = TreeNode(int(level_order[index]))
    nodes.append(root)
    index += 1
    
    while index < len(level_order):
        node_val = level_order[index]
        if node_val != 'null':
            node = TreeNode(int(node_val))
            parent = nodes[(index - 1) // 2]
            if index % 2 == 1:
                parent.left = node
            else:
                parent.right = node
            nodes.append(node)
        index += 1
    
    return root

def path_sum(root, target):
    """统计路径和等于target的路径数量"""
    if not root:
        return 0
    
    # 从当前节点出发计算路径和等于target的路径数量
    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum += node.val
        return (1 if current_sum == target else 0) + dfs(node.left, current_sum) + dfs(node.right, current_sum)
    
    # 总路径数量，既包括以当前节点为起点的路径，又包括递归左右子树
    return dfs(root, 0) + path_sum(root.left, target) + path_sum(root.right, target)

# 主函数
def main():
    n = int(input())  # 节点数量
    nodes = input().split()  # 节点值数组
    target_sum = int(input())  # 目标路径和
    
    root = build_tree(nodes)  # 构建二叉树
    result = path_sum(root, target_sum)  # 获取结果
    print(result)  # 输出结果

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 深度优先搜索，统计路径和等于target的路径数
int dfs(TreeNode* node, int target, int currentSum) {
    if (!node) return 0;
    
    currentSum += node->val;
    int count = (currentSum == target) ? 1 : 0;
    
    count += dfs(node->left, target, currentSum);
    count += dfs(node->right, target, currentSum);
    
    return count;
}

// 统计所有路径和等于target的路径数
int pathSum(TreeNode* root, int target) {
    if (!root) return 0;
    
    // 计算以当前节点为起点的路径
    int count = dfs(root, target, 0);
    
    // 分别计算左子树和右子树的路径
    count += pathSum(root->left, target);
    count += pathSum(root->right, target);
    
    return count;
}

int main() {
    int n;
    cin >> n;
    
    vector<string> nodes(n);
    for (int i = 0; i < n; ++i) {
        cin >> nodes[i];
    }
    
    int targetSum;
    cin >> targetSum;
    
    TreeNode* root = buildTree(nodes);
    cout << pathSum(root, targetSum) << endl;
    
    return 0;
}

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {

    // 根据层次遍历结果构造二叉树
    public static TreeNode buildTree(String[] levelOrder) {
        if (levelOrder.length == 0 || levelOrder[0].equals("null"))
            return null;
        
        List<TreeNode> nodes = new ArrayList<>();
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(levelOrder[index]));
        nodes.add(root);
        index++;
        
        while (index < levelOrder.length) {
            String nodeVal = levelOrder[index];
            if (!nodeVal.equals("null")) {
                TreeNode node = new TreeNode(Integer.parseInt(nodeVal));
                TreeNode parent = nodes.get((index - 1) / 2);
                if (index % 2 == 1)
                    parent.left = node;
                else
                    parent.right = node;
                nodes.add(node);
            }
            index++;
        }
        return root;
    }

    // 深度优先搜索，统计路径和等于target的路径数
    private static int dfs(TreeNode node, int target, int currentSum) {
        if (node == null) return 0;
        
        currentSum += node.val;
        int count = (currentSum == target) ? 1 : 0;
        
        count += dfs(node.left, target, currentSum);
        count += dfs(node.right, target, currentSum);
        
        return count;
    }

    // 统计所有路径和等于target的路径数
    public static int pathSum(TreeNode root, int target) {
        if (root == null) return 0;
        
        int count = dfs(root, target, 0);
        
        count += pathSum(root.left, target);
        count += pathSum(root.right, target);
        
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        
        String[] nodes = sc.nextLine().split(" ");
        int targetSum = sc.nextInt();
        
        TreeNode root = buildTree(nodes);
        System.out.println(pathSum(root, targetSum));
    }
}

题目内容

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

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

输入描述

第一行是一个整数 $n(0 <= n <= 1000)$，表示二叉树中的节点总数。

第二行为一个长度为 $n$ 的二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

第三行是一个整数 $targetSum$。

输出描述

输出一个整数，表示路径和等于 $targetSum$ 的路径数量。

样例1

输入

11
10 5 -3 3 2 null 11 3 -2 null 1
8

输出

3

说明

和等于$8$ 的路径有 $3$ 条，如图所示

样例2

输入

13
5 4 8 11 null 13 4 7 2 null null 5 1
22

输出

3

提示

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