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) } } -- ※ 發信站: 批踢踢實業坊(pttbestweb.org.tw), 來自: 60.248.143.163 (臺灣) ※ 文章網址: https://pttbestweb.org.tw/Marginalman/M.1751279184.A.932