上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 44 MB, 提交时间: 2024-02-25 11:08:37
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode ancestor = root;
while (true) {
if (p.val < ancestor.val && q.val < ancestor.val) {
ancestor = ancestor.left;
} else if (p.val > ancestor.val && q.val > ancestor.val) {
ancestor = ancestor.right;
} else {
break;
}
}
return ancestor;
}
}
rust 解法, 执行用时: 5 ms, 内存消耗: 3.3 MB, 提交时间: 2024-02-25 11:07:50
// 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 x = root.as_ref().unwrap();
let x_val = x.borrow().val;
let p_val = p.as_ref().unwrap().borrow().val;
let q_val = q.as_ref().unwrap().borrow().val;
if p_val < x_val && q_val < x_val { // p 和 q 都在左子树
return Self::lowest_common_ancestor(x.borrow_mut().left.take(), p, q);
}
if p_val > x_val && q_val > x_val { // p 和 q 都在右子树
return Self::lowest_common_ancestor(x.borrow_mut().right.take(), p, q);
}
root // 其它
}
}
java 解法, 执行用时: 6 ms, 内存消耗: 43.9 MB, 提交时间: 2024-02-25 11:07:29
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int x = root.val;
if (p.val < x && q.val < x) { // p 和 q 都在左子树
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > x && q.val > x) { // p 和 q 都在右子树
return lowestCommonAncestor(root.right, p, q);
}
return root; // 其它
}
}
python3 解法, 执行用时: 92 ms, 内存消耗: 19 MB, 提交时间: 2022-07-14 10:38:48
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while (root.val - p.val ) * (root.val - q.val) > 0:
if p.val > root.val:
root = root.right
else:
root = root.left
return root
golang 解法, 执行用时: 16 ms, 内存消耗: 6.9 MB, 提交时间: 2021-07-26 13:56:18
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 利用二叉搜索树的中序遍历(顺序)性质
for (root.Val - p.Val ) * (root.Val - q.Val) > 0 {
if p.Val > root.Val {
root = root.Right
} else {
root = root.Left
}
}
return root
}
golang 解法, 执行用时: 24 ms, 内存消耗: 6.9 MB, 提交时间: 2021-07-05 11:15:09
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 利用二叉搜索树的中序遍历(顺序)性质
for (root.Val - p.Val ) * (root.Val - q.Val) > 0 {
if p.Val > root.Val {
root = root.Right
} else {
root = root.Left
}
}
return root
}
python3 解法, 执行用时: 92 ms, 内存消耗: 18.7 MB, 提交时间: 2021-07-05 11:13:07
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while (root.val - p.val) * (root.val - q.val) > 0:
root = (root.left, root.right)[p.val > root.val]
return root
golang 解法, 执行用时: 20 ms, 内存消耗: 6.9 MB, 提交时间: 2021-07-05 10:56:14
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 利用二叉搜索树的中序遍历(顺序)性质
var res *TreeNode
var dfs func(*TreeNode, *TreeNode, *TreeNode)
dfs = func(r, p1, q1 *TreeNode) {
if (r.Val-p1.Val)*(r.Val-q1.Val) <= 0 {
res = r
} else if r.Val < p1.Val && r.Val < q1.Val {
dfs(r.Right, p1, q1)
} else {
dfs(r.Left, p1, q1)
}
}
dfs(root, p, q)
return res
}
