路径总和 III
题目要求
给定一个二叉树的根节点 root 和一个整数 targetSum，要求计算在这棵二叉树中，节点值之和等于 targetSum 的路径数量。这里的路径定义为一系列节点组成的集合，这些节点在树中从上到下连接而成，不一定要从根节点开始，也不一定要在叶子节点结束。
解题思路
解决这个问题可以采用“双重递归”的策略：
- 外层递归 - 遍历每个节点，将每个节点都当作一次新的路径的起点。
- 内层递归 - 对于每个起点，执行深度优先搜索（DFS），探索所有可能的向下路径。在这个过程中，累加经过的节点值，并与
targetSum进行比较。
具体步骤如下：
- 从根节点开始，对二叉树进行遍历。可以使用前序遍历（根-左-右），因为我们需要从每个节点出发去寻找可能的路径。
- 对于遍历到的每个节点，执行以下操作：
- 调用一个递归函数（内层递归），该函数尝试找出以当前节点为起点，向下延伸的所有路径中，节点值之和等于
targetSum的路径数量。 - 在内层递归中，维护一个当前累计和的变量，每访问一个节点，就将该节点的值加到累计和上。
- 如果当前累计和等于
targetSum，则找到了一条路径，路径计数加一。 - 无论当前累计和是否等于
targetSum，都继续向下递归，直到叶子节点。 - 内层递归需要返回当前节点出发的有效路径数，这样可以将左右子树返回的路径数加到一起。
- 调用一个递归函数（内层递归），该函数尝试找出以当前节点为起点，向下延伸的所有路径中，节点值之和等于
- 将外层递归遍历到的每个节点作为起点得到的路径数累加，得到最终的路径总数。
注意事项：
- 路径方向必须是向下的，即只能从父节点到子节点。
- 路径不必从根节点开始，也不必在叶子节点结束。
- 需要考虑到负数的情况，即路径中可以包含节点值为负数的节点。
这个问题的关键在于理解“双重递归”的概念，即外层递归用于遍历树中的所有节点，内层递归用于从当前节点出发，向下寻找所有可能的路径。通过这种方式，我们可以确保考虑了从树中任意节点出发的所有可能路径。
Golang 版本
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func pathSum(root *TreeNode, targetSum int) int {
if root == nil {
return 0
}
// 外层递归遍历每个节点
return dfs(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}
// 内层递归函数，寻找以node为起点的路径数
func dfs(node *TreeNode, targetSum int) int {
if node == nil {
return 0
}
// 当前路径和
sum := targetSum - node.Val
// 如果当前累计和等于targetSum，则找到一条路径
result := 0
if sum == 0 {
result = 1
}
// 继续递归左右子树
return result + dfs(node.Left, sum) + dfs(node.Right, sum)
}
这段代码定义了一个二叉树节点的结构体TreeNode，并实现了两个函数：pathSum和dfs。pathSum函数是解决问题的主入口，它遍历每个节点，并对每个节点调用dfs函数来寻找以该节点为起点的所有路径。dfs函数则是一个递归函数，用于计算以当前节点为起点，向下延伸的路径中，节点值之和等于targetSum的路径数量。如果当前累计和等于targetSum，则找到一条路径，并继续递归左右子树以寻找更多的路径。最终，pathSum函数返回所有找到的路径数量。
C++版本
#include <iostream>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
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:
// 内层递归函数，寻找以node为起点的路径数
int dfs(TreeNode* node, int targetSum) {
if (!node) return 0;
// 当前路径和
int sum = targetSum - node->val;
// 如果当前累计和等于targetSum，则找到一条路径
int result = sum == 0 ? 1 : 0;
// 继续递归左右子树
return result + dfs(node->left, sum) + dfs(node->right, sum);
}
};
int main() {
// Example of usage:
// TreeNode* root = new TreeNode(10);
// root->left = new TreeNode(5);
// root->right = new TreeNode(-3);
// ... (construct the rest of the tree)
// Solution solution;
// std::cout << solution.pathSum(root, 8) << std::endl;
// ... (remember to delete the allocated nodes to prevent memory leak)
return 0;
}
这段 C++代码定义了一个二叉树节点的结构体TreeNode和一个解决问题的类Solution。Solution类中的pathSum函数是解决问题的主入口，它遍历每个节点，并对每个节点调用dfs函数来寻找以该节点为起点的所有路径。dfs函数是一个递归函数，用于计算以当前节点为起点，向下延伸的路径中，节点值之和等于targetSum的路径数量。如果当前累计和等于targetSum，则找到一条路径，并继续递归左右子树以寻找更多的路径。最终，pathSum函数返回所有找到的路径数量。
在main函数中，你可以构造一个二叉树并调用Solution类的pathSum函数来测试代码。记得在使用完毕后删除分配的节点，以防止内存泄漏。
Python 版本
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
def dfs(node, current_sum):
if not node:
return 0
current_sum += node.val
return (current_sum == targetSum) + dfs(node.left, current_sum) + dfs(node.right, current_sum)
if not root:
return 0
# 从当前节点开始的路径数
paths_from_root = dfs(root, 0)
# 递归子节点
paths_on_left = self.pathSum(root.left, targetSum)
paths_on_right = self.pathSum(root.right, targetSum)
# 总路径数为当前节点开始的路径数加上左右子树的路径数
return paths_from_root + paths_on_left + paths_on_right
# Example usage:
# root = TreeNode(10)
# root.left = TreeNode(5)
# root.right = TreeNode(-3)
# root.left.left = TreeNode(3)
# root.left.right = TreeNode(2)
# root.right.right = TreeNode(11)
# root.left.left.left = TreeNode(3)
# root.left.left.right = TreeNode(-2)
# root.left.right.right = TreeNode(1)
# sol = Solution()
# print(sol.pathSum(root, 8))
这段 Python 代码定义了一个二叉树节点的类TreeNode和一个解决问题的类Solution。Solution类中的pathSum方法是解决问题的主入口，它遍历每个节点，并对每个节点调用dfs函数来寻找以该节点为起点的所有路径。dfs函数是一个递归函数，用于计算以当前节点为起点，向下延伸的路径中，节点值之和等于targetSum的路径数量。如果当前累计和等于targetSum，则找到一条路径，并继续递归左右子树以寻找更多的路径。最终，pathSum方法返回所有找到的路径数量。
在示例使用中，你可以构造一个二叉树并调用Solution类的pathSum方法来测试代码。
Java 版本
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
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, int targetSum) {
if (node == null) return 0;
targetSum -= node.val;
return (targetSum == 0 ? 1 : 0) + dfs(node.left, targetSum) + dfs(node.right, targetSum);
}
}
// Example usage:
// public static void main(String[] args) {
// TreeNode root = new TreeNode(10);
// root.left = new TreeNode(5);
// root.right = new TreeNode(-3);
// root.left.left = new TreeNode(3);
// root.left.right = new TreeNode(2);
// root.right.right = new TreeNode(11);
// root.left.left.left = new TreeNode(3);
// root.left.left.right = new TreeNode(-2);
// root.left.right.right = new TreeNode(1);
// Solution solution = new Solution();
// System.out.println(solution.pathSum(root, 8));
// }
这段 Java 代码定义了一个二叉树节点的类TreeNode和一个解决问题的类Solution。Solution类中的pathSum方法是解决问题的主入口，它遍历每个节点，并对每个节点调用dfs方法来寻找以该节点为起点的所有路径。dfs方法是一个递归方法，用于计算以当前节点为起点，向下延伸的路径中，节点值之和等于targetSum的路径数量。如果当前累计和等于targetSum，则找到一条路径，并继续递归左右子树以寻找更多的路径。最终，pathSum方法返回所有找到的路径数量。
在示例使用中，你可以构造一个二叉树并调用Solution类的pathSum方法来测试代码。
Rust 版本
// Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } use std::rc::Rc; use std::cell::RefCell; pub struct Solution {} impl Solution { pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 { Self::dfs(&root, target_sum) + Self::path_sum_helper(&root, target_sum) } fn path_sum_helper(node: &Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 { if let Some(node) = node { let node = node.borrow(); Self::path_sum(node.left.clone(), target_sum) + Self::path_sum(node.right.clone(), target_sum) } else { 0 } } fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 { if let Some(node) = node { let node = node.borrow(); let val = node.val; let sum = target_sum - val; let mut total_paths = if sum == 0 { 1 } else { 0 }; total_paths += Self::dfs(&node.left, sum); total_paths += Self::dfs(&node.right, sum); total_paths } else { 0 } } } // Example usage: // fn main() { // let root = Some(Rc::new(RefCell::new(TreeNode::new(10)))); // let left = Some(Rc::new(RefCell::new(TreeNode::new(5)))); // let right = Some(Rc::new(RefCell::new(TreeNode::new(-3)))); // root.as_ref().unwrap().borrow_mut().left = left; // root.as_ref().unwrap().borrow_mut().right = right; // // ... continue building the tree ... // println!("{}", Solution::path_sum(root, 8)); // }
这段 Rust 代码定义了一个二叉树节点的结构体TreeNode和一个解决问题的结构体Solution。Solution结构体中的path_sum方法是解决问题的主入口，它遍历每个节点，并对每个节点调用dfs方法来寻找以该节点为起点的所有路径。dfs方法是一个递归方法，用于计算以当前节点为起点，向下延伸的路径中，节点值之和等于target_sum的路径数量。如果当前累计和等于target_sum，则找到一条路径，并继续递归左右子树以寻找更多的路径。最终，path_sum方法返回所有找到的路径数量。
在示例使用中，你可以构造一个二叉树并调用Solution结构体的path_sum方法来测试代码。注意，由于 Rust 的所有权机制，我们通常使用Rc<RefCell<T>>来共享和借用可变的树节点。
总结
这种解法的关键在于，它不仅仅考虑了从根节点到叶节点的路径，还包括了所有可能的从中间节点开始的路径。这是通过在每个节点处重新启动一个新的路径搜索来实现的，这样就能够覆盖树中所有可能的路径。这种方法的时间复杂度相对较高，因为它需要在每个节点处进行深度优先搜索，但它确保了所有可能的路径都被考虑到了。