题解 | #在二叉树中找到两个节点的最近公共祖先#
递归实现
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
function lowestCommonAncestor( root , o1 , o2 ) {
if(!root) return -1
if(root.val===o1 || root.val == o2){
return root.val
}
let left = lowestCommonAncestor(root.left,o1,o2)
let right = lowestCommonAncestor(root.right,o1,o2)
// 如果在左子树中o1和o2都没找到,则肯定在其右子树中,右子树遍历到的那个节点就是最近公共祖先
if(left == -1){
return right
}else if(right == -1){
// 同样如果在右子树中没找到o1和o2,肯定在其左子树
return left
}else{
// 两个都找到了,说明在root的两侧,那么root就是祖先
return root.val
}
}
module.exports = {
lowestCommonAncestor : lowestCommonAncestor
};