使用 Trees 时 Rc<RefCell> 出现问题

Question

我想使用 Rust 解决 Children Sum Property Problem（制作树，使得左 + 右 = 节点）。然而我总是遇到借用检查器。

这个问题是我正在 Rust 中尝试的 DSA 课程的一部分

使用的函数（add_left 和 add_right 添加节点）定义为

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Node {
    value: i32,
    left: Option<Rc<RefCell<Node>>>,
    right: Option<Rc<RefCell<Node>>>,
}
    pub fn add_left(&mut self, value: i32) {
        self.left = Node::new(value).into();
    }
    pub fn add_right(&mut self, value: i32) {
        self.right = Node::new(value).into();
    }

这是我的尝试

pub fn children_sum_property(node: Option<Rc<RefCell<Node>>>) {
    if let Some(node) = node {
        let mut child_sum = 0;
        if let Some(left) = &node.borrow().left {
            child_sum += left.borrow().value;
        }
        if let Some(right) = &node.borrow().right {
            child_sum += right.borrow().value;
        }

        let mut val = node.borrow_mut();
        if child_sum >= val.value {
            val.value = child_sum;
        } else {
            let val_value = val.value; // Store val.value in a temporary variable
            if let Some(left) = val.left.as_mut() {
                left.borrow_mut().value = val_value; // Use the temporary variable here
            }
            if let Some(right) = val.right.as_mut() {
                right.borrow_mut().value = val_value; // And here
            }
        }

        children_sum_property(val.left.clone());
        children_sum_property(val.right.clone());

        let mut total = 0;
        if let Some(left) = &node.borrow().left {
            total += left.borrow().value;
        }
        if let Some(right) = &node.borrow().right {
            total += right.borrow().value;
        }

        if node.borrow().left.is_some() || node.borrow().right.is_some() {
            node.borrow_mut().value = total;
        }
    }
}

但是，它给了我一个错误

error[E0596]: cannot borrow data in dereference of `Ref<'_, binary_tress::Node>` as mutable
   --> src/binary_tress.rs:413:33
    |
413 |             if let Some(left) = node.borrow().left.as_mut() {
    |                                 ^^^^^^^^^^^^^^^^^^ cannot borrow as mutable
    |
    = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Ref<'_, binary_tress::Node>`

我的测试用例是

let mut root = Node::new(10);
root.add_left(5);
root.add_right(3);

Answer 1

问题是你在这里可变地借用

node

：

let mut val = node.borrow_mut();

稍后再在这里借用：

if let Some(left) = &node.borrow().left {
    total += left.borrow().value;
}

第一个借用此时仍然有效，因为

val

仍在范围内，并且您不能同时拥有相同值的两个借用，除非它们都是不可变的。

您可以通过在进行第二次借用之前显式结束存储在

val

中的借用轻松解决此问题，因为在此之后您不再需要

val

：

core::mem::drop(val);

if let Some(left) = &node.borrow().left {
    total += left.borrow().value;
}

(

core::mem::drop()

和

std::mem::drop()

是等价的；我更喜欢

core

版本，因为它可以在更多平台上运行，但大多数Rust程序无论如何都不能在

#[no_std]

平台上运行，我认为

std

是可能更惯用一点，所以你可能更喜欢那个。）

顺便说一句，这种单链树可能不需要

Rc<RefCell<…>>

的力量，因为每个节点只有一个所有者（其父节点） - 您可以只使用

Option<Box<Node>>

来代替。这会更有效，但更重要的是，它会给出更好的错误消息（并且会在编译时而不是运行时捕获这个特定问题）。