235. 二叉搜索树的最近公共祖先
Link
Problem
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是6示例2：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。提示：
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
out := root
for {
if p.Val > out.Val && q.Val > out.Val{
out = out.Right
}else if p.Val < out.Val && q.Val < out.Val{
out = out.Left
}else{
break
}
}
return out
}// Definition for a binary tree node.
// #[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::rc::Rc;
use std::cell::RefCell;
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>>> {
let val_p = p.unwrap().borrow().val;
let val_q = q.unwrap().borrow().val;
let mut root = Rc::clone(root.as_ref().unwrap());
loop {
let val_root = root.borrow().val;
if val_root > val_p && val_root > val_q {
let left = Rc::clone(root.borrow().left.as_ref().unwrap());
root = left;
} else if val_root < val_p && val_root < val_q {
let right = Rc::clone(root.borrow().right.as_ref().unwrap());
root = right;
} else {
break Some(root);
}
}
}
}最后更新于
这有帮助吗？