#P4065. 路径总和Ⅲ
-
ID: 2306
Tried: 219
Accepted: 80
Difficulty: 5
路径总和Ⅲ
题目内容
给定一个二叉树的根节点 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]
- −109<=Node.val<=109
- −1000<=targetSum<=1000
路径总和Ⅲ（前缀和法）
题解思路
这道题目要求我们计算二叉树中所有路径和等于给定目标值 targetSum 的路径数量。可以利用 前缀和 的思路来优化算法。
关键点分析
- 路径的定义：路径不一定从根节点开始，也不一定在叶子节点结束，路径必须是从父节点到子节点进行传递。
- 前缀和的思路：前缀和是一种在数组或树中计算区间和的技巧，可以通过记录路径的前缀和来减少冗余计算，避免重复遍历子树。
前缀和的应用
我们可以通过在遍历树的过程中维护当前路径的前缀和，并使用哈希表记录每个前缀和出现的次数。具体的思想是：
- 在递归过程中，每当访问一个节点时，计算从当前节点到根节点的路径和（前缀和）。
- 如果当前前缀和减去目标值
targetSum结果在哈希表中出现过，说明有路径和等于targetSum，因为从某个先前的节点到当前节点的路径和就是targetSum。 - 通过维护前缀和的哈希表，可以高效地统计满足条件的路径数。
解题步骤
- 前缀和的哈希表：使用哈希表
prefixSum来记录每个前缀和出现的次数，初始时prefixSum[0] = 1，表示从根节点开始就有一个路径和为 0。 - 深度优先搜索（DFS）：通过递归方式遍历树的每个节点，在递归过程中维护当前路径的前缀和。每访问一个节点，就更新前缀和，并检查是否存在某个前缀和为
current_sum - targetSum。 - 路径计数：每当发现某个路径的和等于目标值时，就更新结果计数。
算法步骤
- 从根节点开始，递归地遍历每个节点。
- 对每个节点，计算从该节点到根节点的路径的前缀和。
- 使用哈希表记录出现过的前缀和，每次计算当前路径的前缀和时，检查
prefixSum[current_sum - targetSum]是否存在，若存在，则路径和等于目标值，计数加一。 - 递归地访问左右子树，并更新前缀和。
代码实现
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));
}
}