-
Notifications
You must be signed in to change notification settings - Fork 21
/
iterative.rs
100 lines (76 loc) · 2.62 KB
/
iterative.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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
use crate::data_structures::TreeNode;
pub struct Solution;
// ------------------------------------------------------ snip ------------------------------------------------------ //
use std::cell::RefCell;
use std::rc::Rc;
enum Frame {
Left(Rc<RefCell<TreeNode>>, i32),
Right,
}
impl Solution {
pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, sum: i32) -> Vec<Vec<i32>> {
let mut result = Vec::new();
if let Some(mut node) = root {
let mut sum = sum;
let mut base = Vec::new();
let mut stack = Vec::new();
loop {
let (val, left, right) = {
let node_ref = node.borrow();
(node_ref.val, node_ref.left.clone(), node_ref.right.clone())
};
match (left, right) {
(None, None) => {
if val == sum {
base.push(val);
result.push(base.clone());
base.pop();
}
}
(None, Some(child)) | (Some(child), None) => {
base.push(val);
node = child;
sum -= val;
stack.push(Frame::Right);
continue;
}
(Some(left), Some(right)) => {
base.push(val);
node = left;
sum -= val;
stack.push(Frame::Left(right, sum));
continue;
}
}
loop {
match stack.pop() {
None => return result,
Some(Frame::Left(right, saved_sum)) => {
node = right;
sum = saved_sum;
stack.push(Frame::Right);
break;
}
Some(Frame::Right) => {
base.pop();
}
}
}
}
}
result
}
}
// ------------------------------------------------------ snip ------------------------------------------------------ //
impl super::Solution for Solution {
fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, sum: i32) -> Vec<Vec<i32>> {
Self::path_sum(root, sum)
}
}
#[cfg(test)]
mod tests {
#[test]
fn test_solution() {
super::super::tests::run::<super::Solution>();
}
}