交换一个树的两个子节点

ChariotChai 发表于 2019-06-24 09:14

在用rust刷leet的时候，有很多需要交换树节点的问题。下面是树的定义：

#[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,
        }
    }
}

现在需要一个函数，能够交换某个Option<Rc<RefCell<TreeNode>>>的两个子节点，函数签名如下：

fn swap_children_of_node(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>>;

所以请问版上的朋友：在实现上面的方法时，有没有比较优雅的方法，能够直接交换两个子节点的“指针”而不是使用std::mem::swap直接交换数据（从而提高效率）？

评论区

写评论

chirsz-ever 2019-06-25 17:00

Rc概念上是指向不可变数据的引用计数智能指针，RefCell<T>是直接包装T，大小不比T小，所以只能交换Option里的值了，又考虑到可能是None，直接交换left和right就行了

fn swap_children_of_node(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>>{
    root.map(|rc|{
        RefMut::map(rc.borrow_mut(), |node|{
            std::mem::swap(&mut node.left, &mut node.right);
            node
        });
        rc
    })
}

或者

fn swap_children_of_node(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>>{
    root.map(|mut rc|{
        let node = Rc::get_mut(&mut rc).unwrap().get_mut();
        std::mem::swap(&mut node.left, &mut node.right);
        rc
    })
}

前者更安全。另外，TreeNode这个结构本身也没多大，copy一遍的开销并不是很大。

作者 ChariotChai 2019-06-24 10:41

也许是leet在进行判定检查时需要多处引用？对以下内容的回复：

Krysme 2019-06-24 10:18

有点奇怪，为什么这个树不是Box而是Rc

1 共 3 条评论, 1 页