领扣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
;
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章,本人水平有限,如果有什么说的不对的地方,请指正。 欢迎各位留言讨论,希望小伙伴们都能每天进步一点点。