题目：
后序遍历，当要访问某一个节点时，此时栈中的节点就是从 root 到当前节点的路径上的所有节点。
找到 root 到 p 和 q 的两条路径，然后求这两条路径最后一个相同的节点。
注意这里题目说每个节点值时不同的，因此我们可以直接比较 Rc，这种比较方法比较的时 Rc 指向的值，使用 Rc::ptr_eq 方法可以比较两个 Rc 是否是从同一个 Rc 克隆的
究极无敌恶心的语法：
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
|
struct Solution;
#[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;
use std::rc::Rc;
impl Solution {
pub fn lowest_common_ancestor(
root: Option<Rc<RefCell<TreeNode>>>,
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
if p.is_none() || q.is_none() || root.is_none() {
return None;
}
let p = p.unwrap();
let q = q.unwrap();
let mut stack = VecDeque::new();
let mut curr = root;
let mut last = None;
let mut p_vec = Vec::default();
let mut q_vec = Vec::default();
while curr.is_some() || !stack.is_empty() {
if p_vec.len() > 0 && q_vec.len() > 0 {
break;
}
if let Some(node) = curr {
stack.push_back(node.clone());
curr = node.borrow().left.clone();
} else {
let top = stack.back().unwrap().clone();
let top_borrow = top.borrow();
if top_borrow.right.is_some() && top_borrow.right != last {
curr = top_borrow.right.clone();
} else {
if top_borrow.val == p.borrow().val {
p_vec = stack.iter().cloned().collect();
} else if top_borrow.val == q.borrow().val {
q_vec = stack.iter().cloned().collect();
}
stack.pop_back();
last = Some(top.clone());
curr = None;
}
}
}
let mut index = 0_usize;
let mut res = None;
while index < p_vec.len() && index < q_vec.len() {
if p_vec[index].borrow().val == q_vec[index].borrow().val {
res = Some(p_vec[index].clone());
}
index += 1;
}
res
}
}
fn main() {
println!("Hello, world!");
}
|
