leetcode_rust/
validate_binary_search_tree.rs

1#![allow(dead_code)]
2
3use std::cell::RefCell;
4use std::rc::Rc;
5
6use crate::binary_tree::TreeNode;
7
8// failed: need to consider the minimum boundary
9pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
10    use std::i32;
11    let mut min_val = i32::min_value();
12    _is_valid_bst(root, &mut min_val)
13}
14
15fn _get_left_val(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
16    let mut cur = root;
17    let mut prev = cur.clone();
18    while cur.is_some() {
19        prev = cur.clone();
20        cur = cur.unwrap().borrow().left.clone();
21    }
22
23    prev.unwrap().borrow().val
24}
25
26fn _is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>, mut val: &mut i32) -> bool {
27    match root {
28        None => true,
29        Some(node) => {
30            if _is_valid_bst(node.borrow().left.clone(), &mut val) && *val < node.borrow().val {
31                *val = node.borrow().val;
32                _is_valid_bst(node.borrow().right.clone(), &mut val)
33            } else {
34                false
35            }
36        }
37    }
38}
39
40pub fn is_valid_bst2(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
41    let vals = inorder_traversal(root);
42    if vals.len() == 0 {
43        return true;
44    }
45    for i in 0..vals.len() - 1 {
46        if vals[i] >= vals[i + 1] {
47            return false;
48        }
49    }
50    true
51}
52
53fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
54    let mut res = vec![];
55    inorder(root, &mut res);
56    res
57}
58
59fn inorder(root: Option<Rc<RefCell<TreeNode>>>, mut res: &mut Vec<i32>) {
60    match root {
61        None => {}
62        Some(node) => {
63            inorder(node.borrow().left.clone(), &mut res);
64            res.push(node.borrow().val);
65            inorder(node.borrow().right.clone(), &mut res);
66        }
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test1() {
76        let tree = Some(Rc::new(RefCell::new(TreeNode {
77            val: 1,
78            left: None,
79            right: Some(Rc::new(RefCell::new(TreeNode {
80                val: 2,
81                left: Some(Rc::new(RefCell::new(TreeNode {
82                    val: 3,
83                    left: None,
84                    right: None,
85                }))),
86                right: None,
87            }))),
88        })));
89        assert_eq!(is_valid_bst(tree), false);
90
91        let tree = Some(Rc::new(RefCell::new(TreeNode {
92            val: 1,
93            left: None,
94            right: Some(Rc::new(RefCell::new(TreeNode {
95                val: 3,
96                left: Some(Rc::new(RefCell::new(TreeNode {
97                    val: 2,
98                    left: None,
99                    right: None,
100                }))),
101                right: None,
102            }))),
103        })));
104        assert_eq!(is_valid_bst(tree), true);
105    }
106
107    #[test]
108    fn test2() {
109        let tree = Some(Rc::new(RefCell::new(TreeNode {
110            val: 1,
111            left: None,
112            right: Some(Rc::new(RefCell::new(TreeNode {
113                val: 2,
114                left: Some(Rc::new(RefCell::new(TreeNode {
115                    val: 3,
116                    left: None,
117                    right: None,
118                }))),
119                right: None,
120            }))),
121        })));
122        assert_eq!(is_valid_bst2(tree), false);
123
124        let tree = Some(Rc::new(RefCell::new(TreeNode {
125            val: 1,
126            left: None,
127            right: Some(Rc::new(RefCell::new(TreeNode {
128                val: 3,
129                left: Some(Rc::new(RefCell::new(TreeNode {
130                    val: 2,
131                    left: None,
132                    right: None,
133                }))),
134                right: None,
135            }))),
136        })));
137        assert_eq!(is_valid_bst2(tree), true);
138
139        let tree = Some(Rc::new(RefCell::new(TreeNode {
140            val: 1,
141            left: None,
142            right: None,
143        })));
144        assert_eq!(is_valid_bst2(tree), true);
145        assert_eq!(is_valid_bst2(None), true);
146    }
147}
leetcode_rust/validate_binary_search_tree.rs

leetcode_rust/
validate_binary_search_tree.rs
