Как обрезать пользовательскую реализацию бинарного дерева поиска, не клонируя его? - PullRequest
Новая
       16

Как обрезать пользовательскую реализацию бинарного дерева поиска, не клонируя его?

0 голосов
/ 15 января 2020

LeetCode 669

Я пытаюсь обрезать данное дерево, чтобы иметь только записи в диапазоне [l, r] без клонирования, но это кажется невозможным ...

Это должно быть возможно, я думаю. 

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);
            // `t`'s ownership has just transfer to `n`
            // how to own `t` again after the transfer?
            Some(t.clone())
        } else {
            None
        }
    }
}

детская площадка

Отредактировано

Вопрос выше о том, как получить снова владение после передачи его в другую переменную без использования clone() и to_owned().

И ... Я только что получил решение от rust.cc: использование drop.

1 Ответ

0 голосов
/ 16 января 2020

Получил идеальное решение от ржавчины. cc от @ weirane 

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

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