领扣LintCode算法问题答案-88. 最近公共祖先
目录
88. 最近公共祖先描述样例 1：样例 2：
题解鸣谢
88. 最近公共祖先
描述
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
假设给出的两个节点都在树中存在
样例 1：
输入：{1},1,1
输出：1
解释：
二叉树如下（只有一个节点）:
1
LCA(1,1) = 1
样例 2：
输入：{4,3,7,#,#,5,6},3,5
输出：4
解释：
二叉树如下:
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
题解
public class Solution {
public TreeNode
lowestCommonAncestor(TreeNode root
, TreeNode A
, TreeNode B
) {
if (root
== null
) {
return null
;
}
if (root
== A
|| root
== B
) {
return root
;
}
TreeNode left
= lowestCommonAncestor(root
.left
, A
, B
);
TreeNode right
= lowestCommonAncestor(root
.right
, A
, B
);
if (left
!= null
&& right
!= null
) {
return root
;
}
if (left
!= null
) {
return left
;
}
if (right
!= null
) {
return right
;
}
return null
;
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
