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

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // write code here
    //与JZ68的区别，二叉树不同于二叉搜索树，值没有规律
    if(!root)return
    if(root.val==o1) return root.val
    if(root.val==o2) return root.val
    let left=lowestCommonAncestor(root.left,o1,o2)
    let right=lowestCommonAncestor(root.right,o1,o2)
    if(left&&right) return root.val
    if(left) return left
    if(right) return right
}

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

function lowestCommonAncestor(root, o1, o2) {
    // write code here
    var dfs = function (root, p, q) {
        if (root == null || root.val == p || root.val == q) {
            return root;
        }
        var left = dfs(root.left, p, q);
        var right = dfs(root.right, p, q);
        if (left && right) {
            return root;
        } else {
            return left ? left : right;
        }
    };
    var res = dfs(root, o1, o2);
    return res.val;
}

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    if (!root) return NaN;
    if ([o1, o2].includes(root.val)) return root.val;
    const left = lowestCommonAncestor(root.left, o1, o2);
    const right = lowestCommonAncestor(root.right, o1, o2);
    if (!left) return right;
    if (!right) return left;
    if (!left && !right) return NaN;
    return root.val;
}

/*
 * 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 ) {
    // write code here
    if(root===null || root.val== o1 || root.val== o2){ //单根、没有左右子树
        return root
    }
    //递归获取左右子树
    const left = lowestCommonAncestor( root.left ,  o1 ,  o2 );
    const right = lowestCommonAncestor( root.right ,  o1 ,  o2 );
    //左右子树都不为空，则返回根节点
    if(left != null && right != null){
        return root.val
    }
    //左右子树其中一个不为空，则放回相应子树的查找结果
    return left != null ? left : right
    //三元运算符的表达式：
    //(expression1)  ?  (expression2)  :  (expression3)
    //在  expression1  求值为  true  时的值为  expression2  ，在expression1  求值是  false  时的值为  expression3

//     if(left==null){
//         return right;
//     }else if(right==null){
//         return left;
//     }else{
//         return root.val;
//     }
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // 遇到叶子节点返回
    if (root === null) {
        return null
    }
    // 如果p或q为根节点，则p或q为最近公共祖先
    if (root.val === o1 || root.val === o2) {
        return root.val
    }
    // 在左子树寻找p和q的最近公共祖先
    const leftRes = lowestCommonAncestor(root.left, o1, o2)
    // 在右子树寻找q和q的最近公共祖先
    const rightRes = lowestCommonAncestor(root.right, o1, o2)
    // 如果p和q分属两侧，则根节点为最近公共祖先
    if (leftRes && rightRes) {
        return root.val
    }
    // 如果左子树有值，则最近公共祖先在左子树，否则，在右子树
    return leftRes ? leftRes : rightRes
}