CODEWITHSUNDEEP
rust
Jerry Yuan
Jerry Yuan

Reputation: 765

type annotations needed for `&Borrowed`

I am trying to compile the LeetCode question 98's rust code in https://rustgym.com/leetcode/98 However, I receive an error in this line: let node = node.borrow();:

type annotations needed for `&Borrowed`
type must be known at this point
rustcE0282
s0098_validate_binary_search_tree.rs(66, 17): consider giving `node` the explicit type `&Borrowed`, where the type parameter `Borrowed` is specified

However, Leetcode has no problem to compile it. Here is the Code.

use std::rc::Rc;
use std::cell::RefCell;
type TreeLink = Option<Rc<RefCell<TreeNode>>>;
trait Inorder {
    fn inorder(&self, visit: &mut dyn FnMut(i32));
}
impl Inorder for TreeLink {
    fn inorder(&self, visit: &mut dyn FnMut(i32)) {
        if let Some(node) = self {
            let node = node.borrow();
            Self::inorder(&node.left, visit);
            visit(node.val);
            Self::inorder(&node.right, visit);
        }    
    }
}

impl Solution {
    pub fn is_valid_bst(root: TreeLink) -> bool {
        let mut prev: Option<i32> = None;
        let mut res = true;
        root.inorder(&mut |x| {
            if let Some(y) = prev {
                if x <= y {
                    res = false;
                }
            }
            prev = Some(x);
        });
        res
    }
}

I am using rustc 1.55.0 (c8dfcfe04 2021-09-06). I think it may be a bug in compiler.

Upvotes: 8

Views: 2229

Answers (4)

Jason
Jason

Reputation: 107

  1. Your code is fine. I passed 98' by you code without any change.
    enter image description here

  2. I met the same question by adding the redundant code use std::borrow::Borrow;. So when I deleted use std::borrow::Borrow;, everything is fine~
    enter image description here

Upvotes: 10

陈靖珏
陈靖珏

Reputation: 31

I had the same problem, after I checked, the culprit was the "clion" error auto-import, try to delete the "import" section and re-import, the problem should be solved.

Upvotes: 3

Jerry Yuan
Jerry Yuan

Reputation: 765

It is very strange. Today I compile again without any changes. Now the issue is gone. I think it may be caused by a hidden bug in rust compiler. Thank you for your help!

Upvotes: -4

Zeppi
Zeppi

Reputation: 1235

The solution https://rustgym.com/leetcode/98 use rustgym_util::*; with define TreeNode, TreeLink, etc.

struct Solution;
//
//--Begin rustgym_util:: def----------------------------------
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct TreeNode {
    pub val: i32,
    pub left: TreeLink,
    pub right: TreeLink,
}
pub type TreeLink = Option<Rc<RefCell<TreeNode>>>;

#[macro_export]
macro_rules! tree {
    ($e:expr) => {
        TreeLink::leaf($e)
    };
    ($e:expr, $l:expr, $r:expr) => {
        TreeLink::branch($e, $l, $r)
    };
}

use std::cell::RefCell;
use std::rc::Rc;

pub trait TreeMaker {
    fn branch(val: i32, left: TreeLink, right: TreeLink) -> TreeLink {
        Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
    }
    fn leaf(val: i32) -> TreeLink {
        Some(Rc::new(RefCell::new(TreeNode {
            val,
            left: None,
            right: None,
        })))
    }
}

impl TreeMaker for TreeLink {}
//
//--Endrustgym_util:: def----------------------------------

trait Inorder {
    fn inorder(&self, visit: &mut dyn FnMut(i32));
}

impl Inorder for TreeLink {
    fn inorder(&self, visit: &mut dyn FnMut(i32)) {
        if let Some(node) = self {
            let node = node.borrow();
            Self::inorder(&node.left, visit);
            visit(node.val);
            Self::inorder(&node.right, visit);
        }
    }
}

impl Solution {
    fn is_valid_bst(root: TreeLink) -> bool {
        let mut prev: Option<i32> = None;
        let mut res = true;
        root.inorder(&mut |x| {
            if let Some(y) = prev {
                if x <= y {
                    res = false;
                }
            }
            prev = Some(x);
        });
        res
    }
}

#[test]
fn test() {
    let root = tree!(2, tree!(1), tree!(3));
    let res = true;
    assert_eq!(Solution::is_valid_bst(root), res);
    let root = tree!(5, tree!(1), tree!(4, tree!(3), tree!(6)));
    let res = false;
    assert_eq!(Solution::is_valid_bst(root), res);
}

How you have defined TreeNode in your side?

Upvotes: 0

Related Questions