我正在尝试使用Rust解决一些Leetcode问题。然而,我在LeetCode的TreeNode
实现中遇到了一些困难。
use std::cell::RefCell;
use std::rc::Rc;
// TreeNode data structure
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
如果我想进行中序遍历,如何拆开
TreeNode
的 Option<Rc<RefCell<TreeNode>>>
对象,访问其 .val
.left
.right
并将它们作为输入传递到递归函数中?我尝试过:
pub struct Solution;
impl Solution {
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ret: Vec<i32> = vec![];
match root {
Some(V) => Solution::helper(&Some(V), &mut ret),
None => (),
}
ret
}
fn helper(node: &Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<i32>) {
match node {
None => return,
Some(V) => {
// go to the left branch
Solution::helper(
(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
.into_inner()
.left,
ret,
);
// push root value on the vector
ret.push(Rc::try_unwrap(Rc::clone(V)).unwrap_err().into_inner().val);
// go right branch
Solution::helper(
(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
.into_inner()
.right,
ret,
);
}
}
}
}
fn main() {}
(Playground)编译器报错:
error[E0308]: mismatched types
--> src/lib.rs:42:21
|
42 | / (*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
43 | | .into_inner()
44 | | .left,
| |_____________________________^ expected reference, found enum `std::option::Option`
|
= note: expected type `&std::option::Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>`
found type `std::option::Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>`
help: consider borrowing here
|
42 | &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
43 | .into_inner()
44 | .left,
|
但是,如果我尝试这个建议,它也会抱怨:
error[E0507]: cannot move out of an `Rc`
--> src/lib.rs:42:22
|
42 | &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of an `Rc`
error[E0507]: cannot move out of data in a `&` reference
--> src/lib.rs:42:22
|
42 | &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| |
| cannot move out of data in a `&` reference
| cannot move
TreeNode
可以使用Box
替代Rc<RefCell<..>>
,对吗?如果答案是肯定的,那么这个版本对于树结构来说更好吗?请告诉我这个评论是否值得一个全新的问题。 - Raydel MirandaBox
或Rc/RefCell
在Rust中实现相同数据结构的情况。我对Rust相对较新,这些东西引起了我的注意。在这个练习中,不需要共享值或改变节点值(Rc-RefCell的完美用例),因此,也许由于我对Rust的经验太少,我错过了什么,也许与性能有关,我不知道。 - Raydel MirandaBox
而不是Rc/RefCell
*更少出错,更清晰易读。 https://ricardomartins.cc/2016/06/08/interior-mutability - Raydel MirandaBox
。 - Shepmaster