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

这是 LeetCode 129 题 “求根节点到叶节点数字之和” 的 Rust 实现。

题目描述

给你一个二叉树的根节点
“root”，树中每个节点都存放有一个
“0” 到
“9” 之间的数字。

每条从根节点到叶节点的路径都代表一个数字（例如路径
“1 -> 2 -> 3” 表示数字
“123”）。

计算从根节点到叶节点生成的所有数字之和。

解题思路：深度优先搜索（DFS）

利用递归进行深度优先遍历：

1. 传递累加值：在递归过程中，将“从根节点到当前节点父节点所组成的数字”作为参数
   “current_sum” 向下传递。
2. 计算当前节点值：到达当前节点时，更新路径数字为
   “current_sum * 10 + node.val”。
3. 判断叶子节点：如果当前节点是叶子节点（左右子节点均为空），则直接返回该路径组成的数字。
4. 递归左右子树：如果不是叶子节点，则继续递归计算左子树和右子树的结果，并将它们相加返回。

说明：Rust 中 LeetCode 的二叉树通常定义为
“Option<Rc<RefCell>>”，我们通过
“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: Option<Rc<RefCell>>,
// pub right: Option<Rc<RefCell>>,
// }
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }

impl Solution {
pub fn sum_numbers(root: Option<Rc<RefCell>>) -> i32 {
Self::dfs(root, 0)
}

fn dfs(root: Option<Rc<RefCell<TreeNode>>>, 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: Option<Rc<RefCell>>,
pub right: Option<Rc<RefCell>>,
}

impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}

struct Solution;

impl Solution {
pub fn sum_numbers(root: Option<Rc<RefCell>>) -> i32 {
Self::dfs(root, 0)
}

fn dfs(root: Option<Rc<RefCell<TreeNode>>>, 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 3
let 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” 在二叉树中的内存管理逻辑吗？