元宝 LeetCode 129. 求根节点到叶节点数字之和 Rust实现

这是 LeetCode 129 题 “求根节点到叶节点数字之和” 的 Rust 实现。题目描述给你一个二叉树的根节点“root”树中每个节点都存放有一个“0” 到“9” 之间的数字。每条从根节点到叶节点的路径都代表一个数字例如路径“1 - 2 - 3” 表示数字“123”。计算从根节点到叶节点生成的所有数字之和。解题思路深度优先搜索DFS利用递归进行深度优先遍历传递累加值在递归过程中将“从根节点到当前节点父节点所组成的数字”作为参数“current_sum” 向下传递。计算当前节点值到达当前节点时更新路径数字为“current_sum * 10 node.val”。判断叶子节点如果当前节点是叶子节点左右子节点均为空则直接返回该路径组成的数字。递归左右子树如果不是叶子节点则继续递归计算左子树和右子树的结果并将它们相加返回。说明Rust 中 LeetCode 的二叉树通常定义为“OptionRcRefCell”我们通过“borrow()” 来读取节点数据通过“clone()” 来传递子节点的智能指针。LeetCode 风格核心代码use std::rc::Rc;use std::cell::RefCell;// 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 {// TreeNode {// val,// left: None,// right: None// }// }// }impl Solution {pub fn sum_numbers(root: OptionRcRefCell) - i32 {Self::dfs(root, 0)}fn dfs(root: OptionRcRefCellTreeNode, current_sum: i32) - i32 { match root { None 0, Some(node) { // 借用节点读取数据 let node_ref node.borrow(); let new_sum current_sum * 10 node_ref.val; // 如果是叶子节点直接返回当前路径组成的数字 if node_ref.left.is_none() node_ref.right.is_none() { return new_sum; } // 否则递归计算左右子树并相加结果 // 注意这里使用 clone() 增加引用计数而不是转移所有权 Self::dfs(node_ref.left.clone(), new_sum) Self::dfs(node_ref.right.clone(), new_sum) } } }}完整可运行示例含本地测试如果你想在本地运行测试可以使用以下完整代码use std::rc::Rc;use std::cell::RefCell;// 二叉树节点定义#[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 {TreeNode { val, left: None, right: None }}}struct Solution;impl Solution {pub fn sum_numbers(root: OptionRcRefCell) - i32 {Self::dfs(root, 0)}fn dfs(root: OptionRcRefCellTreeNode, current_sum: i32) - i32 { match root { None 0, Some(node) { let node_ref node.borrow(); let new_sum current_sum * 10 node_ref.val; if node_ref.left.is_none() node_ref.right.is_none() { return new_sum; } Self::dfs(node_ref.left.clone(), new_sum) Self::dfs(node_ref.right.clone(), new_sum) } } }}fn main() {// 示例 1: [1,2,3]// 1// /// 2 3let root Rc::new(RefCell::new(TreeNode::new(1)));let left Rc::new(RefCell::new(TreeNode::new(2)));let right Rc::new(RefCell::new(TreeNode::new(3)));root.borrow_mut().left Some(left);root.borrow_mut().right Some(right);println!(“示例1结果: {}”, Solution::sum_numbers(Some(root))); // 输出: 25// 示例 2: [4,9,0,5,1] // 4 // / \ // 9 0 // / \ // 5 1 let root2 Rc::new(RefCell::new(TreeNode::new(4))); let left2 Rc::new(RefCell::new(TreeNode::new(9))); let right2 Rc::new(RefCell::new(TreeNode::new(0))); let left2_left Rc::new(RefCell::new(TreeNode::new(5))); let left2_right Rc::new(RefCell::new(TreeNode::new(1))); left2.borrow_mut().left Some(left2_left); left2.borrow_mut().right Some(left2_right); root2.borrow_mut().left Some(left2); root2.borrow_mut().right Some(right2); println!(示例2结果: {}, Solution::sum_numbers(Some(root2))); // 输出: 1026}复杂度分析时间复杂度O(n)其中 n 是二叉树的节点数每个节点恰好被访问一次。空间复杂度O(h)其中 h 是二叉树的高度。主要为递归调用栈所占用的空间最坏情况下链状树为 O(n)。 延展思考除了递归 DFS你还可以使用 迭代法BFS/DFS 借助栈或队列 来解决避免递归栈溢出的风险。需要我为你提供迭代法使用栈的 Rust 实现或者帮你详细解析“Rc” 在二叉树中的内存管理逻辑吗