LeetCode 107. 二叉树的层序遍历 II Rust 实现思路和 Python 版本一致先用 BFS 自顶向下逐层收集最后把结果整体反转得到自底向上的层序遍历。Rust 中需要处理 OptionRcRefCell 的所有权和借用问题队列使用 VecDeque。Rust 代码usestd::rc::Rc;usestd::cell::RefCell;usestd::collections::VecDeque;// Definition for a binary tree node.// #[derive(Debug, PartialEq, Eq)]// pub struct TreeNode {// pub val: i32,// pub left: OptionRcRefCellTreeNode,// pub right: OptionRcRefCellTreeNode,// }//// impl TreeNode {// #[inline]// pub fn new(val: i32) - Self {// TreeNode {// val,// left: None,// right: None,// }// }// }implSolution{pubfnlevel_order_bottom(root:OptionRcRefCellTreeNode)-VecVeci32{letmutres:VecVeci32Vec::new();ifroot.is_none(){returnres;}letmutqueue:VecDequeRcRefCellTreeNodeVecDeque::new();queue.push_back(root.unwrap());while!queue.is_empty(){letlevel_sizequeue.len();letmutlevelVec::with_capacity(level_size);for_in0..level_size{letnode_rcqueue.pop_front().unwrap();letnodenode_rc.borrow();level.push(node.val);// 克隆 Rc增加引用计数将子节点加入队列ifletSome(left)node.left.clone(){queue.push_back(left);}ifletSome(right)node.right.clone(){queue.push_back(right);}}res.push(level);}// 自底向上反转结果res.reverse();res}}关键点说明队列元素类型VecDequeRcRefCell。Rc 提供共享所有权RefCell 提供内部可变性虽然这里只读但树节点定义如此。借用与克隆从队列取出 Rc 后用 borrow() 获得 Ref 来读取 val。访问 left / right 时因为 node 是 Ref不能移动出字段所以用 .clone() 克隆 OptionRc…这只是增加 Rc 的引用计数开销很小。反转结果最后 res.reverse() 原地反转得到自底向上的顺序。复杂度分析项目 复杂度时间 O(n)每个节点入队出队一次空间 O(n)队列最大宽度 结果数组示例验证输入 3 / \ 9 20 / \ 15 7 BFS 自顶向下[[3], [9, 20], [15, 7]] 反转后 [[15, 7], [9, 20], [3]]另一种写法DFS 递归可选usestd::rc::Rc;usestd::cell::RefCell;implSolution{pubfnlevel_order_bottom(root:OptionRcRefCellTreeNode)-VecVeci32{letmutres:VecVeci32Vec::new();fndfs(node:OptionRcRefCellTreeNode,depth:usize,res:mutVecVeci32){ifletSome(n)node{letnn.borrow();ifdepthres.len(){res.push(Vec::new());}res[depth].push(n.val);dfs(n.left.as_ref(),depth1,res);dfs(n.right.as_ref(),depth1,res);}}dfs(root.as_ref(),0,mutres);res.reverse();res}}DFS 同样是 O(n) 时间但递归深度最坏为 O(n)实际刷题推荐 BFS。
