236. Lowest Common Ancestor of a Binary Tree
题目：
找两个人的最近共同祖先
思路：
这题目可以分成两个部分
一个是回传 一个是判断
回传的部分
前面先判断空值回传 None/nullptr
后面是找到就回传找到的节点
判断的部分
之后过了判断没被阻挡
就能判断有没有共同祖先
如果节点往下左右的回传都有找到人
代表这个节点就是最近的祖先
算动物配种的近亲交配也能使用这个方法
Code:
use std::cell::RefCell;
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>>> {
fn dfs(
node: Option<Rc<RefCell<TreeNode>>>,
p: &Option<Rc<RefCell<TreeNode>>>,
q: &Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
let n = match node {
Some(n) => n,
None => return None,
};
if let Some(p_node) = p.as_ref() {
if Rc::ptr_eq(&n, p_node) {
return Some(n.clone());
}
}
if let Some(q_node) = q.as_ref() {
if Rc::ptr_eq(&n, q_node) {
return Some(n.clone());
}
}
let n_ref = n.borrow();
let left = dfs(n_ref.left.clone(), p, q);
let right = dfs(n_ref.right.clone(), p, q);
match (left, right) {
(Some(_), Some(_)) => Some(n.clone()),
(Some(l), None) => Some(l),
(None, Some(r)) => Some(r),
_ => None,
}
}
dfs(root, &p, &q)
}
}