2022-05-22：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
如何时间复杂度O(N)，额外空间复杂度O(1)，解决最低公共祖先问题?
力扣236。二叉树的最近公共祖先。
答案2022-05-23：
莫里斯遍历。主要是修改rust代码。
rust代码修改如下：
代码语言：rust复制use std::cell::RefCell;
use std::rc::Rc;
fn main() {
let mut head = Some(Rc::new(RefCell::new(TreeNode::new(1))));
let mut left_left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
let mut left_right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
head.as_ref().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
head.as_ref().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
head.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow_mut()
.left = Some(Rc::clone(&left_left.as_ref().unwrap()));
head.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow_mut()
.right = Some(Rc::clone(&left_right.as_ref().unwrap()));
let ans = Solution::lowest_common_ancestor(
Some(Rc::clone(&head.as_ref().unwrap())),
Some(Rc::clone(&left_left.as_ref().unwrap())),
Some(Rc::clone(&left_right.as_ref().unwrap())),
);
if ans.is_none() {
println!("ans = 空");
} else {
println!("ans val = {}", ans.as_ref().unwrap().borrow().val);
}
println!("-----------------");
println!("head = {}", head.as_ref().unwrap().borrow().val);
println!(
"head.left = {}",
head.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow()
.val
);
println!(
"head.right = {}",
head.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap()
.borrow()
.val
);
println!(
"head.left.left = {}",
head.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow()
.val
);
println!(
"head.left.right = {}",
head.as_ref()
.unwrap()
.borrow()
.left
.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap()
.borrow()
.val
);
}
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
pub fn new(val: i32) -> Self {
Self {
val,
left: None,
right: None,
}
}
}
pub struct Solution {}
// 力扣里提交以下的代码
impl Solution {
// 该方法亮点在于：时间复杂度O(N)，额外空间复杂度O(1)
pub fn lowest_common_ancestor(
mut head: Option<Rc<RefCell<TreeNode>>>,
mut o1: Option<Rc<RefCell<TreeNode>>>,
mut o2: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
// if (findFirst(o1.left, o1, o2) != null || findFirst(o1.right, o1, o2) != null) {
// return o1;
// }
if !find_first(
if o1.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&o1.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
|| !find_first(
if o1.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&o1.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
{
return if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
};
}
// if (findFirst(o2.left, o1, o2) != null || findFirst(o2.right, o1, o2) != null) {
// return o2;
// }
if !find_first(
if o2.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&o2.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
|| !find_first(
if o2.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&o2.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
{
return if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
};
}
//left_aim := findFirst(head, o1, o2)
let mut left_aim = find_first(
if head.is_none() {
None
} else {
Some(Rc::clone(&head.as_ref().unwrap()))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
);
// TreeNode cur = head;
let mut cur = if head.is_none() {
None
} else {
Some(Rc::clone(&head.as_ref().unwrap()))
};
// TreeNode most_right = null;
let mut most_right: Option<Rc<RefCell<TreeNode>>> = None;
// TreeNode ans = null;
let mut ans: Option<Rc<RefCell<TreeNode>>> = None;
//for cur != nil {
while !cur.is_none() {
// most_right = cur.left;
most_right = if cur.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
};
//if most_right != nil {
if !most_right.is_none() {
//while most_right.right != null && most_right.right != cur {
while !most_right.as_ref().unwrap().borrow().right.is_none()
&& !is_eq(
&Some(Rc::clone(
&most_right
.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap(),
)),
&cur,
)
{
// most_right = most_right.right;
most_right = if most_right.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&most_right
.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap(),
))
};
}
//if (most_right.right == null) {
if most_right.as_ref().unwrap().borrow().right.is_none() {
// most_right.right = cur;
most_right.as_ref().unwrap().borrow_mut().right = if cur.is_none() {
None
} else {
Some(Rc::clone(&cur.as_ref().unwrap()))
};
// cur = cur.left;
cur = if cur.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
};
continue;
} else {
//most_right.right = null;
most_right.as_ref().unwrap().borrow_mut().right = None;
//if (findLeftAim(cur.left, left_aim)) {
if find_left_aim(
if cur.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
},
if left_aim.is_none() {
None
} else {
Some(Rc::clone(&left_aim.as_ref().unwrap()))
},
) {
//if (ans == null && findFirst(left_aim.right, o1, o2) != null) {
if ans.is_none()
&& !find_first(
if left_aim.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&left_aim
.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
{
//ans = left_aim;
ans = if left_aim.is_none() {
None
} else {
Some(Rc::clone(&left_aim.as_ref().unwrap()))
};
}
// left_aim = cur;
left_aim = if cur.is_none() {
None
} else {
Some(Rc::clone(&cur.as_ref().unwrap()))
};
}
}
}
// cur = cur.right;
cur = if cur.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
};
}
if !ans.is_none() {
return ans;
} else {
if !find_first(
if left_aim.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&left_aim.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
},
if o1.is_none() {
None
} else {
Some(Rc::clone(&o1.as_ref().unwrap()))
},
if o2.is_none() {
None
} else {
Some(Rc::clone(&o2.as_ref().unwrap()))
},
)
.is_none()
{
return Some(Rc::clone(&left_aim.as_ref().unwrap()));
} else {
return Some(Rc::clone(&head.as_ref().unwrap()));
}
}
}
}
fn find_left_aim(
mut head: Option<Rc<RefCell<TreeNode>>>,
mut left_aim: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
let mut tail = reverse_edge(Some(Rc::clone(&head.as_ref().unwrap())));
//TreeNode cur = tail;
let mut cur = if tail.is_none() {
None
} else {
Some(Rc::clone(&tail.as_ref().unwrap()))
};
// boolean ans = false;
let mut ans = false;
while !cur.is_none() {
if is_eq(&cur, &left_aim) {
ans = true;
}
// cur = cur.right;
cur = if cur.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
};
}
reverse_edge(Some(Rc::clone(&tail.as_ref().unwrap())));
return ans;
}
fn reverse_edge(mut from: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
//TreeNode pre = null;
let mut pre: Option<Rc<RefCell<TreeNode>>> = None;
//TreeNode next = null;
let mut next: Option<Rc<RefCell<TreeNode>>> = None;
while !is_eq(&from, &None) {
// next = from.right;
next = if from.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&from.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
};
// from.right = pre;
from.as_ref().unwrap().borrow_mut().right = if pre.is_none() {
None
} else {
Some(Rc::clone(&pre.as_ref().unwrap()))
};
// pre = from;
pre = if from.is_none() {
None
} else {
Some(Rc::clone(&from.as_ref().unwrap()))
};
// from = next;
from = if next.is_none() {
None
} else {
Some(Rc::clone(&next.as_ref().unwrap()))
};
}
return pre;
}
fn find_first(
mut head: Option<Rc<RefCell<TreeNode>>>,
mut o1: Option<Rc<RefCell<TreeNode>>>,
mut o2: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
//if head == nil {
if head.is_none() {
return None;
}
//cur := head
let mut cur: Option<Rc<RefCell<TreeNode>>> = Some(Rc::clone(&head.as_ref().unwrap()));
//var most_right *TreeNode
let mut most_right: Option<Rc<RefCell<TreeNode>>> = None;
//var first *TreeNode
let mut first: Option<Rc<RefCell<TreeNode>>> = None;
//for cur != nil {
while !cur.is_none() {
//most_right = cur.left;
most_right = if cur.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
};
//if most_right != nil {
if !most_right.is_none() {
while !most_right.as_ref().unwrap().borrow().right.is_none()
&& !is_eq(&most_right.as_ref().unwrap().borrow().right, &cur)
{
//most_right = most_right.right;
most_right = if most_right.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&most_right
.as_ref()
.unwrap()
.borrow()
.right
.as_ref()
.unwrap(),
))
};
}
if is_eq(&most_right.as_ref().unwrap().borrow().right, &None) {
if is_eq(&first, &None) && (is_eq(&cur, &o1) || is_eq(&cur, &o2)) {
// first = cur;
first = if cur.is_none() {
None
} else {
Some(Rc::clone(&cur.as_ref().unwrap()))
};
}
// most_right.right = cur;
most_right.as_ref().unwrap().borrow_mut().right = if cur.is_none() {
None
} else {
Some(Rc::clone(&cur.as_ref().unwrap()))
};
// cur = cur.left;
cur = if cur.as_ref().unwrap().borrow().left.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().left.as_ref().unwrap(),
))
};
continue;
} else {
//most_right.right = nil;
most_right.as_ref().unwrap().borrow_mut().right = None;
}
} else {
//if first == nil && (cur == o1 || cur == o2) {
if is_eq(&first, &None) && (is_eq(&cur, &o1) || is_eq(&cur, &o2)) {
// first = cur;
first = if cur.as_ref().is_none() {
None
} else {
Some(Rc::clone(&cur.as_ref().unwrap()))
};
}
}
// cur = cur.right;
cur = if cur.as_ref().unwrap().borrow().right.is_none() {
None
} else {
Some(Rc::clone(
&cur.as_ref().unwrap().borrow().right.as_ref().unwrap(),
))
};
}
return first;
}
fn is_eq(o1: &Option<Rc<RefCell<TreeNode>>>, o2: &Option<Rc<RefCell<TreeNode>>>) -> bool {
if o1.is_none() && o2.is_none() {
return true;
}
if o1.is_none() || o2.is_none() {
return false;
}
return o1.as_ref().unwrap().borrow().val == o2.as_ref().unwrap().borrow().val;
}执行结果如下：
在这里插入图片描述
