/
same_tree.rs
119 lines (104 loc) · 3.85 KB
/
same_tree.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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
use std::cell::RefCell;
use std::{collections::VecDeque, rc::Rc};
pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
let mut stack_p: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
let mut stack_q: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
let mut is_equal = true;
if p.is_none() && q.is_none() {
return true;
}
if (p.is_none() && q.is_some()) || (p.is_some() && q.is_none()) {
return false;
}
stack_p.push_back(Rc::clone(p.as_ref().unwrap()));
stack_q.push_back(Rc::clone(q.as_ref().unwrap()));
while !stack_p.is_empty() && !stack_q.is_empty() && is_equal {
let pop_p = stack_p.pop_front();
let pop_q = stack_q.pop_front();
match pop_p {
Some(ref the_p) => match pop_q {
Some(ref the_q) => {
if the_p.as_ref().borrow().val != the_q.as_ref().borrow().val {
is_equal = false;
} else {
// the left
match the_p.as_ref().borrow().left {
Some(ref the_p_left) => match the_q.as_ref().borrow().left {
Some(ref the_q_left) => {
stack_p.push_back(Rc::clone(the_p_left));
stack_q.push_back(Rc::clone(the_q_left));
}
None => {
is_equal = false;
}
},
None => {
if the_q.as_ref().borrow().left.is_some() {
is_equal = false
}
}
}
match the_p.as_ref().borrow().right {
Some(ref the_p_right) => match the_q.as_ref().borrow().right {
Some(ref the_q_right) => {
stack_p.push_back(Rc::clone(the_p_right));
stack_q.push_back(Rc::clone(the_q_right))
}
None => {
is_equal = false;
}
},
None => {
if the_q.as_ref().borrow().right.is_some() {
is_equal = false;
}
}
}
}
}
None => {
is_equal = false;
}
},
None => {
if pop_q.as_ref().is_none() {
is_equal = false;
}
}
}
}
return is_equal;
}
pub fn recursive_is_same(
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
match (p, q) {
(Some(pn), None) => false,
(None, Some(qn)) => false,
(Some(pn), Some(qn)) => {
let val_same = pn.borrow().val == qn.borrow().val;
val_same
&& recursive_is_same(pn.borrow().left.clone(), qn.borrow().left.clone())
&& recursive_is_same(pn.borrow().right.clone(), qn.borrow().right.clone())
}
(None, None) => true,
}
}