/
recursive.rs
76 lines (63 loc) · 2.42 KB
/
recursive.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
use crate::data_structures::TreeNode;
pub struct Solution;
// ------------------------------------------------------ snip ------------------------------------------------------ //
use std::cell::RefCell;
use std::rc::Rc;
enum State<'a> {
Ok(&'a [i32]),
Error,
Fatal,
}
impl Solution {
fn helper<'a>(node: Option<&RefCell<TreeNode>>, voyage: &'a [i32], result: &mut Vec<i32>) -> State<'a> {
node.map_or(State::Ok(voyage), |node| {
let node = node.borrow();
let (&first, voyage) = voyage.split_first().unwrap();
if node.val == first {
match Self::helper(node.left.as_deref(), voyage, result) {
State::Ok(voyage) => match Self::helper(node.right.as_deref(), voyage, result) {
State::Ok(voyage) => State::Ok(voyage),
State::Error | State::Fatal => State::Fatal,
},
State::Error => match Self::helper(node.right.as_deref(), voyage, result) {
State::Ok(voyage) => match Self::helper(node.left.as_deref(), voyage, result) {
State::Ok(voyage) => {
result.push(first);
State::Ok(voyage)
}
State::Error | State::Fatal => State::Fatal,
},
State::Error | State::Fatal => State::Fatal,
},
State::Fatal => State::Fatal,
}
} else {
State::Error
}
})
}
pub fn flip_match_voyage(root: Option<Rc<RefCell<TreeNode>>>, voyage: Vec<i32>) -> Vec<i32> {
let mut result = Vec::new();
match Self::helper(root.as_deref(), &voyage, &mut result) {
State::Ok(_) => {}
State::Error | State::Fatal => {
result.clear();
result.push(-1);
}
}
result
}
}
// ------------------------------------------------------ snip ------------------------------------------------------ //
impl super::Solution for Solution {
fn flip_match_voyage(root: Option<Rc<RefCell<TreeNode>>>, voyage: Vec<i32>) -> Vec<i32> {
Self::flip_match_voyage(root, voyage)
}
}
#[cfg(test)]
mod tests {
#[test]
fn test_solution() {
super::super::tests::run::<super::Solution>();
}
}