【Question】如何正确地复用这个TreeNode？

wfxr 发表于 2019-12-31 12:22

下面是leetcode上面一个题目的Rust solution. #897 Increasing Order Search Tree

我想在注释的地方用Relink的方式复用当前的TreeNode，而不是创建一个新的TreeNode。也就是说，把当前这个root节点的left置为None，将其作为left_tail的right子节点，这样遍历就可以复用原来Tree所有的节点。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn increasing_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let node = Some(Rc::new(RefCell::new(TreeNode::new(0))));
        Self::do_increasing_bst(root, node.clone());
        node.unwrap().borrow().right.clone()
    }
    pub fn do_increasing_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        tail: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root {
            let mut left_tail = Self::do_increasing_bst(node.borrow().left.clone(), tail.clone());
            // TODO: How to reuse the current node (i.e. root) without creating a new one?
            let right_tail = Some(Rc::new(RefCell::new(TreeNode::new(node.borrow().val))));
            left_tail.unwrap().borrow_mut().right = right_tail.clone();
            Self::do_increasing_bst(node.borrow().right.clone(), right_tail.clone())
        } else {
            tail
        }
    }
}

尝试了很久，要么过不了编译器，要么会在运行时因为可变借用检查失败而挂掉。有没有人可以帮忙指点一下应该如何实现呢？

评论区

写评论

作者 wfxr 2020-01-16 13:47

抱歉很久没登录论坛。完全没想到可以通过Option的get方法来解决这个问题，学到了，谢谢解答！

对以下内容的回复：

pfcoder 2020-01-03 11:17

赞一个！对以下内容的回复：

不过我搞明白了，之前的borrow冲突，其实是由于右子树遍历入口，对right 和 node 在参数级同时引用，使用一个临时变量可以解决这种冲突，如下：

pub fn do_increasing_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        tail: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if root != None {
            let left_tail = Self::do_increasing_bst(
                root.as_ref().unwrap().borrow_mut().left.clone(),
                tail.clone(),
            );

            //Self::ptr_node(&root).left = None;
            //Self::ptr_node(&left_tail).right = root.clone();

            root.as_ref().unwrap().borrow_mut().left = None;
            left_tail.as_ref().unwrap().borrow_mut().right = root.clone();

            // change is here
            let right = root.as_ref().unwrap().borrow().right.clone();
            Self::do_increasing_bst(right, root.clone())
        } else {
            // println!("t:{}", tail.as_ref().unwrap().borrow().val);
            tail
        }
    }

AlephAlpha 2020-01-03 09:34

呃，

impl Solution {
    pub fn increasing_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let node = Some(Rc::new(RefCell::new(TreeNode::new(0))));
        Self::do_increasing_bst(root, node.clone());
        node.unwrap().borrow().right.clone()
    }
    pub fn do_increasing_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        tail: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root {
            let mut left_tail = Self::do_increasing_bst(node.borrow_mut().left.take(), tail.clone());
            left_tail.unwrap().borrow_mut().right = Some(node.clone());
            let right = node.borrow_mut().right.take();
            Self::do_increasing_bst(right, Some(node))
        } else {
            tail
        }
    }
}

pfcoder 2020-01-02 21:11

貌似只能unsafe了，递归始终在borrow

impl Solution {
    pub fn increasing_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let node = Some(Rc::new(RefCell::new(TreeNode::new(0))));
        Self::do_increasing_bst(root, node.clone());
        node.unwrap().borrow().right.clone()
    }

    #[inline]
    fn ptr_node<'a>(n: &'a Option<Rc<RefCell<TreeNode>>>) -> &'a mut TreeNode {
        let t = n.as_ref().unwrap().as_ptr();
        unsafe { &mut *t }
    }

    pub fn do_increasing_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        tail: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if root != None {
            let left_tail =
                Self::do_increasing_bst(root.as_ref().unwrap().borrow().left.clone(), tail.clone());

            Self::ptr_node(&root).left = None;
            Self::ptr_node(&left_tail).right = root.clone();

            Self::do_increasing_bst(root.as_ref().unwrap().borrow().right.clone(), root.clone())
        } else {
            tail
        }
    }
}

作者 wfxr 2019-12-31 17:13

对以下内容的回复：

和Option关系不大吧？

AlephAlpha 2019-12-31 15:43

提示：Option 类型有个 take 方法，可以把 option 中的内容取出来。

1 共 6 条评论, 1 页