【所有权】如何不用 clone() / to_owned() 实现二叉树的 trim?

clearloop 发表于 2020-01-15 12:26

impl Solution {
    pub fn trim_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        l: i32,
        r: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        Self::h(&root, l, r)
    }

    fn h(
      t: &Option<Rc<RefCell<TreeNode>>>, 
      l: i32, 
      r: i32
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(t) = t {
            let mut n = t.borrow_mut();
            if n.val < l {
                return Self::h(&n.right, l, r);
            }
            if n.val > r {
                return Self::h(&n.left, l, r);
            }
            n.left = Self::h(&n.left, l, r);
            n.right = Self::h(&n.right, l, r);
            // What if not cloning.
            Some(t.clone())
        } else {
            None
        }
    }
}

贴一下 playground

评论区

写评论

作者 clearloop 2020-01-16 15:09

服了，大佬们，刷了几天 leetcode，我现在开始怀疑我以前写的都是假 Rust LOL 对以下内容的回复：

weirane 2020-01-16 14:59

写了一个不用返回的，另外用 drop 也可以达到大括号的效果。

playground

对以下内容的回复：

shaitao 2020-01-16 10:43

我认为还是用unsafe吧, 把所有权交给树而不是交给节点

作者 clearloop 2020-01-15 23:30

有没有啥办法能够不返回 Option<Rc<RefCell<TreeNode>>>，直接进行 trim?

作者 clearloop 2020-01-15 23:07

太骚了，这个花括号

AlephAlpha 2020-01-15 21:00

t 是个 Rc，复制它并不会把整棵树复制一遍，开销并不大，没有必要避免。

真的不想用 clone 的话，可以这样:

impl Solution {
    pub fn trim_bst(
        mut root: Option<Rc<RefCell<TreeNode>>>,
        l: i32,
        r: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        Self::h(&mut root, l, r)
    }

    fn h(
      t: &mut Option<Rc<RefCell<TreeNode>>>, 
      l: i32, 
      r: i32
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(t) = t.take() {
            {
                let mut n = t.borrow_mut();
                if n.val < l {
                    return Self::h(&mut n.right, l, r);
                }
                if n.val > r {
                    return Self::h(&mut n.left, l, r);
                }
                n.left = Self::h(&mut n.left, l, r);
                n.right = Self::h(&mut n.right, l, r);
            }
            Some(t)
        } else {
            None
        }
    }
}

IWANABETHATGUY 2020-01-15 20:05

unsafe

1 共 7 条评论, 1 页