领扣LintCode算法问题答案-1311. 二叉搜索树的最近公共祖先
发布日期:2021-06-30 17:10:41
浏览次数:2
分类:技术文章
本文共 1143 字,大约阅读时间需要 3 分钟。
领扣LintCode算法问题答案-1311. 二叉搜索树的最近公共祖先
目录
1311. 二叉搜索树的最近公共祖先
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root ={6,2,8,0,4,7,9,#,#,3,5}
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
样例 1:
输入:{6,2,8,0,4,7,9,#,#,3,5}28输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
样例 2:
输入:{6,2,8,0,4,7,9,#,#,3,5}24输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
题解
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */public class Solution { /** * @param root: root of the tree * @param p: the node p * @param q: the node q * @return: find the LCA of p and q */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // write your code here if(p.val>root.val&&q.val>root.val){ return lowestCommonAncestor(root.right,p,q); } if(p.val
鸣谢
非常感谢你愿意花时间阅读本文章,本人水平有限,如果有什么说的不对的地方,请指正。
欢迎各位留言讨论,希望小伙伴们都能每天进步一点点。
转载地址:https://le-yi.blog.csdn.net/article/details/108907529 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月13日 23时41分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Camera-ready ddl
2019-04-30
NLP之N-Gram模型
2019-04-30
CIFAR-100数据集
2019-04-30
Tiny Imagenet 数据集
2019-04-30
Knowledge Amalgamation 知识合并
2019-04-30
autossh
2019-04-30
CUB-200鸟类数据集
2019-04-30
MMLab工具箱 —— Hook机制
2019-04-30
MMLab工具箱 —— Runner类
2019-04-30
动态语言 vs. 静态语言
2019-04-30
Python反射机制
2019-04-30
YAPF —— Python代码格式化工具
2019-04-30
MMOCR——config文件
2019-04-30
NCCL
2019-04-30
pip install git+
2019-04-30
UGC 用户产生内容
2019-04-30
ranger
2019-04-30
slurm
2019-04-30
xfce4
2019-04-30
xrdp
2019-04-30