题解 | #在二叉树中找到两个节点的最近公共祖先#

递归实现

/*
 * 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
};