I implemented the Iterative solution by C:
(Tricky: Using a pointer to pointer method, it is unnecessary to record the parent of the deleted node)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* deleteNode(struct TreeNode* root, int key){
struct TreeNode** curr = &root; // the address of the pointer variable `root`
while (*curr != NULL) {
if ((*curr)->val < key) {
curr = &(*curr)->right;
} else if ((*curr)->val > key) {
curr = &(*curr)->left;
} else {
if (NULL != (*curr)->left && NULL != (*curr)->right) {
struct TreeNode* tmp = *curr;
// find the successor of `tmp`
curr = &(*curr)->right;
while ((*curr)->left != NULL) {
curr = &(*curr)->left;
}
tmp->val = (*curr)->val; // swap
*curr = (*curr)->right;
} else {
if (NULL != (*curr)->right) {
*curr = (*curr)->right;
} else {
*curr = (*curr)->left; // NULL or left subtree
}
}
break;
}
}
return root;
}
Then I want to implement it by Rust as fallows:
// Definition for a binary tree node.
// #[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
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::Ordering;
impl Solution {
pub fn delete_node(mut root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
let mut curr: &mut Option<Rc<RefCell<TreeNode>>> = &mut root;
while let Some(ref mut node) = curr {
let val: i32 = node.borrow().val;
match val.cmp(&key) {
Ordering::Less => curr = &mut curr.as_mut().unwrap().borrow_mut().right,
Ordering::Greater => curr = &mut curr.as_mut().unwrap().borrow_mut().left,
Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
(false, false) => *curr = None,
(false, true) => *curr = node.borrow_mut().right.take(),
(true, false) => *curr = node.borrow_mut().left.take(),
(true, true) => {
let mut succ = &mut curr.as_mut().unwrap().borrow_mut().right;
while let Some(ref mut node) = succ { // succ.as_mut().unwrap()
if node.borrow_mut().left.is_some() {
succ = &mut node.borrow_mut().left;
}
}
curr.as_mut().unwrap().borrow_mut().val = succ.as_mut().unwrap().borrow().val;
*succ = succ.as_mut().unwrap().borrow_mut().right;
}
}
}
}
root
}
}
Compile Error:
Line 28, Char 47: temporary value dropped while borrowed (solution.rs)
|
28 | Ordering::Less => curr = &mut curr.as_mut().unwrap().borrow_mut().right,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -
| | |
| | temporary value is freed at the end of this statement
| | ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, tree_node::TreeNode>`
| creates a temporary which is freed while still in use
| a temporary with access to the borrow is created here ...
|
= note: consider using a `let` binding to create a longer lived value
help: consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped
|
46 | };
| +
Line 29, Char 50: temporary value dropped while borrowed (solution.rs)
|
29 | Ordering::Greater => curr = &mut curr.as_mut().unwrap().borrow_mut().left,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -
| | |
| | temporary value is freed at the end of this statement
| | ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, tree_node::TreeNode>`
| creates a temporary which is freed while still in use
| a temporary with access to the borrow is created here ...
|
= note: consider using a `let` binding to create a longer lived value
help: consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped
|
46 | };
| +
Line 31, Char 39: cannot assign to `*curr` because it is borrowed (solution.rs)
|
25 | while let Some(ref mut node) = curr {
| ------------ borrow of `*curr` occurs here
...
30 | Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
| ------------- a temporary with access to the borrow is created here ...
31 | (false, false) => *curr = None,
| ^^^^^ assignment to borrowed `*curr` occurs here
...
44 | }
| - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, tree_node::TreeNode>`
|
help: consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped
|
46 | };
| +
Line 32, Char 38: cannot assign to `*curr` because it is borrowed (solution.rs)
|
25 | while let Some(ref mut node) = curr {
| ------------ borrow of `*curr` occurs here
...
30 | Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
| ------------- a temporary with access to the borrow is created here ...
31 | (false, false) => *curr = None,
32 | (false, true) => *curr = node.borrow_mut().right.take(),
| ^^^^^ assignment to borrowed `*curr` occurs here
...
44 | }
| - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, tree_node::TreeNode>`
|
help: consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped
|
46 | };
| +
Line 33, Char 38: cannot assign to `*curr` because it is borrowed (solution.rs)
|
25 | while let Some(ref mut node) = curr {
| ------------ borrow of `*curr` occurs here
...
30 | Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
| ------------- a temporary with access to the borrow is created here ...
...
33 | (true, false) => *curr = node.borrow_mut().left.take(),
| ^^^^^ assignment to borrowed `*curr` occurs here
...
44 | }
| - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, tree_node::TreeNode>`
|
help: consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped
|
46 | };
| +
Line 35, Char 45: cannot borrow `*curr` as mutable more than once at a time (solution.rs)
|
25 | while let Some(ref mut node) = curr {
| ------------ first mutable borrow occurs here
...
30 | Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
| ------------- a temporary with access to the first borrow is created here ...
...
35 | let mut succ = &mut curr.as_mut().unwrap().borrow_mut().right;
| ^^^^^^^^^^^^^ second mutable borrow occurs here
...
44 | }
| - ... and the first borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, tree_node::TreeNode>`
Line 36, Char 35: cannot use `*succ` because it was mutably borrowed (solution.rs)
|
36 | while let Some(ref mut node) = succ { // succ.as_mut().unwrap()
| ^^^^^------------^
| | |
| | borrow of `succ.0` occurs here
| use of borrowed `succ.0`
| borrow later used here
Line 36, Char 40: cannot borrow `succ.0` as mutable more than once at a time (solution.rs)
|
36 | while let Some(ref mut node) = succ { // succ.as_mut().unwrap()
| ^^^^^^^^^^^^ `succ.0` was mutably borrowed here in the previous iteration of the loop
Line 38, Char 45: temporary value dropped while borrowed (solution.rs)
|
38 | ... succ = &mut node.borrow_mut().left;
| ^^^^^^^^^^^^^^^^^ -
| | |
| | temporary value is freed at the end of this statement
| | ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, tree_node::TreeNode>`
| creates a temporary which is freed while still in use
| a temporary with access to the borrow is created here ...
|
= note: consider using a `let` binding to create a longer lived value
Line 41, Char 25: cannot borrow `*curr` as mutable more than once at a time (solution.rs)
|
25 | while let Some(ref mut node) = curr {
| ------------ first mutable borrow occurs here
...
30 | Ordering::Equal => match (node.borrow().left.is_some(), node.borrow().right.is_some()) {
| ------------- a temporary with access to the first borrow is created here ...
...
41 | curr.as_mut().unwrap().borrow_mut().val = succ.as_mut().unwrap().borrow().val;
| ^^^^^^^^^^^^^ second mutable borrow occurs here
...
44 | }
| - ... and the first borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, tree_node::TreeNode>`
Line 41, Char 67: cannot borrow `*succ` as mutable more than once at a time (solution.rs)
|
36 | while let Some(ref mut node) = succ { // succ.as_mut().unwrap()
| ------------ first mutable borrow occurs here
...
41 | curr.as_mut().unwrap().borrow_mut().val = succ.as_mut().unwrap().borrow().val;
| ^^^^^^^^^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
Line 42, Char 25: cannot assign to `*succ` because it is borrowed (solution.rs)
|
42 | *succ = succ.as_mut().unwrap().borrow_mut().right;
| ^^^^^ ----------------------------------- - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, tree_node::TreeNode>`
| | |
| | borrow of `*succ` occurs here
| | a temporary with access to the borrow is created here ...
| assignment to borrowed `*succ` occurs here
Line 42, Char 33: cannot borrow `*succ` as mutable more than once at a time (solution.rs)
|
36 | while let Some(ref mut node) = succ { // succ.as_mut().unwrap()
| ------------ first mutable borrow occurs here
...
42 | *succ = succ.as_mut().unwrap().borrow_mut().right;
| ^^^^^^^^^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
Line 42, Char 33: cannot move out of dereference of `RefMut<'_, tree_node::TreeNode>` (solution.rs)
|
42 | *succ = succ.as_mut().unwrap().borrow_mut().right;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ move occurs because value has type `Option<Rc<RefCell<tree_node::TreeNode>>>`, which does not implement the `Copy` trait
|
help: consider borrowing the `Option`'s content
|
42 | *succ = succ.as_mut().unwrap().borrow_mut().right.as_ref();
| +++++++++
Some errors have detailed explanations: E0499, E0503, E0506, E0507, E0716.
For more information about an error, try `rustc --explain E0499`.
error: could not compile `prog` due to 14 previous errors
mv: cannot stat '/leetcode/rust_compile/target/release/prog': No such file or directory
Is there any way to solve this problem(temporary value dropped while borrowed
)?
Ordering::Less => curr = &mut curr.as_mut().unwrap().borrow_mut().right,
Thanks!