元宝 LeetCode 113.路径总和 || rust实现

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