Rust learning notes 3
The best way to learn is with doing and with failures.
Maximum Depth of Binary Tree
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn node_depth(node: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match node {
Some(node) => {
let node = node.borrow();
max(
node_depth(node.left),
node_depth(node.right),
) + 1
},
_ => 0,
}
}
node_depth(root)
}
And the compiler complains:
cannot move out of borrowed content
node_depth(node.left)
cannot move out of data in a `&` reference
The reason is that, node is reference to the TreeNode, which means it is a borrowed content. However, the signature of the node_depth() declared the first argument as Option<Rc<RefCell<TreeNode>>> which means it will consume the input value. So the complier complains that we cannot move move the conent from a borrowed object (reference).
There are two ways to fix the problem, one is with the clone() method to create an cloned object that you own. Like below
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn node_depth(node: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match node {
Some(node) => {
let node = node.borrow();
max(
node_depth(node.left.clone()),
node_depth(node.right.clone()),
) + 1
},
_ => 0,
}
}
node_depth(root)
}
The other way to fix it is to declare the arguments as the reference (not to consume the content)
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn node_depth(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
match node {
Some(node) => {
let node = node.borrow();
max(
node_depth(&node.left),
node_depth(&node.right),
) + 1
},
_ => 0,
}
}
node_depth(&root)
}
One interesting to note is that the node is a type of Rc, why can we call the borrow method which belongs to RefCell. The reason is that, the signature of the borrow() call takes as the parameter &self which is reference to RefCell. And because Rc implements the Deref trait, the reference to Rc will be converted to the reference to RefCell due to the mechanism of Deref coercion. In other way, Rc will automatically implments the immutatable methods of RefCell due to the mechanism of Deref coercion
Another solution for this problem is like below, referenced here
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn node_depth(node: Option<&Rc<RefCell<TreeNode>>>) -> i32 {
match node {
Some(node) => {
let node = node.borrow();
max(
node_depth(node.left.as_ref()),
node_depth(node.right.as_ref()),
) + 1
},
_ => 0,
}
}
node_depth(root.as_ref())
}
The trick here is that the as_ref() call can convert &Option<T> to Option<&T>
Insufficiant nodes
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: &Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
&Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
match node.borrow().left {
Some(nodeleft) => {
match node.borrow().right {
Some(noderight) => {
let p1 = helper(&Some(noderight),limit-node.borrow().val);
let p2 = helper(&Some(nodeleft),limit-node.borrow().val);
if (p1 == p2) {
&None
}
else {
root
}
},
None => {
let p1 = helper(&Some(nodeleft),limit-node.borrow().val);
if let Some(v) = p1 {
root
} else {
&None
}
},
}
},
None => {
match node.borrow().right {
Some(noderight) => {
let p1 = helper(&Some(noderight),limit-node.borrow().val);
if let Some(v) = p1 {
root
} else {
&None
}
},
None => {
if node.borrow().val < limit {
&None
} else {
root
}
},
}
},
}
} else { root }
}
let rc = helper(&root,limit);
rc.clone()
}
This code has lot of problems. The first one is
match node.borrow().left
cannot move out of borrowed content
some (nodeleft)
data moved here
If we change the code to below
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: &Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
&Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
match &node.borrow().left {
Some(nodeleft) => {
match &node.borrow().right {
Some(noderight) => {
let p1 = helper(&Some(*noderight),limit-node.borrow().val);
let p2 = helper(&Some(*nodeleft),limit-node.borrow().val);
if (p1 == p2) {
&None
}
else {
root
}
},
None => {
let p1 = helper(&Some(*nodeleft),limit-node.borrow().val);
if let Some(v) = p1 {
root
} else {
&None
}
},
}
},
None => {
match &node.borrow().right {
Some(noderight) => {
let p1 = helper(&Some(*noderight),limit-node.borrow().val);
if let Some(v) = p1 {
root
} else {
&None
}
},
None => {
if node.borrow().val < limit {
&None
} else {
root
}
},
}
},
}
} else { root }
}
let rc = helper(&root,limit);
rc.clone()
}
The compiler will then complain
temporary value dropped while borrowed
let p1 = helper(&Some(*noderight),limit-node.borrow().val);
^^^^^^^^^^^^
creates a temporary which is freed while still in use
The following code can compile
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: &Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
&Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
let cur = node.borrow_mut();
match &cur.left {
Some(nodeleft) => {
match &cur.right {
Some(noderight) => {
cur.left = helper(&cur.right,limit-cur.val);
cur.right = helper(&cur.left,limit-cur.val);
if p1.is_none() && p2.is_none() {
&None
}
else {
root
}
},
None => {
let p1 = helper(&cur.left,limit-cur.val);
if let Some(v) = p1 {
root
} else {
&None
}
},
}
},
None => {
match &cur.right {
Some(noderight) => {
let p1 = helper(&cur.right,limit-cur.val);
if let Some(v) = p1 {
root
} else {
&None
}
},
None => {
if cur.val < limit {
&None
} else {
root
}
},
}
},
}
} else { root }
}
let rc = helper(&root,limit);
rc.clone()
}
But it outputs an incorrect answer. The reason is that it does not update the children.
But if we update the children, there will be the following complain
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: &Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
&Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
let mut cur = node.borrow_mut();
match &cur.left {
Some(nodeleft) => {
match &cur.right {
Some(noderight) => {
let p1 = helper(&cur.right,limit-cur.val);
let p2 = helper(&cur.left,limit-cur.val);
if p1.is_none() {
cur.right = None;
}
if p2.is_none() {
cur.left = None;
}
if p1.is_none() && p2.is_none() {
&None
}
else {
root
}
},
None => {
let p1 = helper(&cur.left,limit-cur.val);
if let Some(v) = p1 {
root
} else {
&None
}
},
}
},
None => {
match &cur.right {
Some(noderight) => {
let p1 = helper(&cur.right,limit-cur.val);
if let Some(v) = p1 {
root
} else {
&None
}
},
None => {
if cur.val < limit {
&None
} else {
root
}
},
}
},
}
} else { root }
}
let rc = helper(&root,limit);
rc.clone()
}
The compiler says
error[E0502]: cannot borrow `cur` as mutable because it is also borrowed as immutable
--> src/solution.rs:104:41
|
101 | let p1 = helper(&cur.right,limit-cur.val);
| --- immutable borrow occurs here
...
104 | cur.right = None;
| ^^^ mutable borrow occurs here
...
109 | if p1.is_none() && p2.is_none() {
| -- immutable borrow later used here
After a lot of fixes, the below code runs and is correct
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
let mut cur = node.borrow_mut();
match &cur.left {
Some(nodeleft) => {
match &cur.right {
Some(noderight) => {
let p1 = helper(cur.right.clone(),limit-cur.val);
let p2 = helper(cur.left.clone(),limit-cur.val);
if p1.is_none() {
cur.right = None;
}
if p2.is_none() {
cur.left = None;
}
if p1.is_none() && p2.is_none() {
None
}
else {
Some(node.clone())
}
},
None => {
let p1 = helper(cur.left.clone(),limit-cur.val);
if let Some(v) = p1 {
Some(node.clone())
} else {
None
}
},
}
},
None => {
match &cur.right {
Some(noderight) => {
let p1 = helper(cur.right.clone(),limit-cur.val);
if let Some(v) = p1 {
Some(node.clone())
} else {
None
}
},
None => {
if cur.val < limit {
None
} else {
Some(node.clone())
}
},
}
},
}
} else { None }
}
let rc = helper(root,limit);
rc.clone()
}
An improved version
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
let mut cur = node.borrow_mut();
if cur.left.is_some() && cur.right.is_some() {
let p1 = helper(cur.right.clone(),limit-cur.val);
let p2 = helper(cur.left.clone(),limit-cur.val);
if p1.is_none() {
cur.right = None;
}
if p2.is_none() {
cur.left = None;
}
if p1.is_none() && p2.is_none() {
None
}
else {
Some(node.clone())
}
} else if cur.left.is_some() {
let p1 = helper(cur.left.clone(),limit-cur.val);
if let Some(v) = p1 {
Some(node.clone())
} else {
None
}
} else if cur.right.is_some() {
let p1 = helper(cur.right.clone(),limit-cur.val);
if let Some(v) = p1 {
Some(node.clone())
} else {
None
}
} else {
if cur.val < limit {
None
} else {
Some(node.clone())
}
}
} else { None }
}
let rc = helper(root,limit);
rc.clone()
}
An further improved version
pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
fn helper(root: &Option<Rc<RefCell<TreeNode>>>, limit: i32) ->
Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root {
let mut cur = node.borrow_mut();
if cur.left.is_none() && cur.right.is_none() {
if cur.val < limit {
None
} else {
Some(node.clone())
}
} else {
cur.right = helper(&cur.right,limit-cur.val);
cur.left = helper(&cur.left,limit-cur.val);
if cur.right.is_none() && cur.left.is_none() {
None
}
else {
Some(node.clone())
}
}
} else { None }
}
helper(&root,limit)
}