LeetCode 113（Path Sum II）是一道经典的 深度优先搜索（DFS）+ 回溯 题目。
解题思路
- 从根节点开始遍历，用一个
“path” 动态记录从根到当前节点的路径。 - 用
“current_sum” 记录当前路径上节点值的总和。 - 当遇到叶子节点时，检查路径总和是否等于
“targetSum”。如果相等，将当前
“path” 的拷贝加入结果集。 - 回溯：在递归返回前，将当前节点从
“path” 中弹出，以便探索其他分支。
Rust 实现代码
在 LeetCode 中，
“TreeNode” 通常定义为
“Option<Rc<RefCell>>”。以下是可以直接提交的完整代码：
// 假设 LeetCode 已提供 TreeNode 的定义：
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell>>,
// pub right: Option<Rc<RefCell>>,
// }
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self { … }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn path_sum(root: Option<Rc<RefCell>>, target_sum: i32) -> Vec<Vec> {
let mut result: Vec<Vec> = Vec::new();
let mut path: Vec = Vec::new();
if let Some(node) = root { Solution::dfs(node, target_sum, 0, &mut path, &mut result); } result } // 深度优先搜索 fn dfs( node: Rc<RefCell<TreeNode>>, target_sum: i32, current_sum: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>> ) { // 取出当前节点的值，并加入路径 let val = node.borrow().val; path.push(val); let new_sum = current_sum + val; // 先克隆左右子节点的引用（避免持有 borrow 导致递归时 panic） let left = node.borrow().left.clone(); let right = node.borrow().right.clone(); // 判断是否为叶子节点 if left.is_none() && right.is_none() { if new_sum == target_sum { // 找到一条合法路径，克隆当前路径存入结果 result.push(path.clone()); } } else { // 递归遍历左右子树 if let Some(left_node) = left { Solution::dfs(left_node, target_sum, new_sum, path, result); } if let Some(right_node) = right { Solution::dfs(right_node, target_sum, new_sum, path, result); } } // 回溯：离开当前节点，将其从路径中移除 path.pop(); }}
关键点解析（Rust 特性）
“Rc<RefCell>” 的使用：
- LeetCode 的树节点使用
“Rc”（引用计数）允许多个所有者，
“RefCell” 提供内部可变性。 - 在递归前，通过
“.clone()” 获取左右子节点的
“Option<Rc<…>>”，这样不会长期持有
“RefCell” 的借用，避免运行时 panic。
回溯与所有权：
“path” 通过
“&mut Vec” 传递，在递归前后分别执行
“push” 和
“pop”，手动维护路径状态。
“result.push(path.clone())” 这里必须
“clone”，因为
“path” 后续还会被修改。
3. 效率：
- 时间复杂度：O(N)，每个节点访问一次。
- 空间复杂度：O(N)（递归栈深度及存储路径所需的空间）。
如果你希望改成迭代法（使用显式栈）或者想了解如何处理 i32 溢出等边界情况，也可以告诉我！
