rustgym/leetcode/
_98_validate_binary_search_tree.rs

1struct Solution;
2use rustgym_util::*;
3
4trait Inorder {
5    fn inorder(&self, visit: &mut dyn FnMut(i32));
6}
7
8impl Inorder for TreeLink {
9    fn inorder(&self, visit: &mut dyn FnMut(i32)) {
10        if let Some(node) = self {
11            let node = node.borrow();
12            Self::inorder(&node.left, visit);
13            visit(node.val);
14            Self::inorder(&node.right, visit);
15        }
16    }
17}
18
19impl Solution {
20    fn is_valid_bst(root: TreeLink) -> bool {
21        let mut prev: Option<i32> = None;
22        let mut res = true;
23        root.inorder(&mut |x| {
24            if let Some(y) = prev {
25                if x <= y {
26                    res = false;
27                }
28            }
29            prev = Some(x);
30        });
31        res
32    }
33}
34
35#[test]
36fn test() {
37    let root = tree!(2, tree!(1), tree!(3));
38    assert_eq!(Solution::is_valid_bst(root), true);
39    let root = tree!(5, tree!(1), tree!(4, tree!(3), tree!(6)));
40    assert_eq!(Solution::is_valid_bst(root), false);
41}