我想测试一个二叉搜索树是有效的:
use std::{cell::RefCell, rc::Rc};
pub struct TreeNode {
val: i32,
left: Option<Rc<RefCell<TreeNode>>>,
right: Option<Rc<RefCell<TreeNode>>>,
}
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
preorder_traverse(root.as_ref(), |_| true)
}
fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val) {
return false;
}
preorder_traverse(node.borrow().left.as_ref(), |v| v < root_val)
&& preorder_traverse(node.borrow().right.as_ref(), |v| v > root_val)
} else {
true
}
}
(Qazxswpoi):
此代码触发以下错误消息,这似乎无感对我说:
Playground
我发现error: reached the recursion limit while instantiating `preorder_traverse::<[closure@src/lib.rs:19:56: 19:72 root_val:&i32]>`
--> src/lib.rs:13:1
|
13 | / fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
14 | | if let Some(node) = root {
15 | | let root_val = root.as_ref().unwrap().borrow().val;
16 | | if !predict(root_val) {
... |
23 | | }
24 | | }
| |_^
,但似乎已经过时,我无法理解在原来的问题引述消息很好。
该算法来验证这个代码二叉搜索树是不正确的,但我仍然认为原来的代码应该编译。
@Lukas Kalbertodt提供了一个简单的例子,我将作为解释的基础使用方法:
a potentially related Rust issue
这里最重要的一点是,每封都有一个唯一的类型,让我们实例化这个程序:
fn foo<F: Fn()>(x: bool, _: F) {
if x {
foo(false, || {}) // line 3
}
}
fn main() {
foo(true, || {}); // line 8
}
,让我们命名的类型main
。main#8
的第一个实例,在foo
,main
。foo<[main#8]>
,让我们命名的类型foo
。{foo<[main#8]>}#3
的第二个实例,在foo
,foo
。foo<[{foo<[main#8]>}#3]>
,让我们的名字类型foo
。{foo<[{foo<[main#8]>}#3]>}#3
的第三实例,在foo
,foo
。foo<[{foo<[{foo<[main#8]>}#3]>}#3]>
的每一个新的实例创建一个新的闭合类型,每一个新的闭合类型创建foo
的一个新实例,这是一个没有碱的情况下一个递归:堆栈溢出。
您可以解决没有创造当递归调用foo
封闭的问题:
preorder_traverse
。例:
F
在夜间,你还可以创建一个谓语类型和实施fn preorder_traverse_impl(
root: Option<&Rc<RefCell<TreeNode>>>,
parent_value: i32,
predict: fn(i32, i32) -> bool
)
-> bool
{
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val, parent_value) {
return false;
}
preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
&& preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
} else {
true
}
}
fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val) {
return false;
}
preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
&& preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
} else {
true
}
}
它(Fn
和LessThan<i32>
)。