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)
}
}