/*
 * 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 ) {
    const node = traverse(root, o1, o2);
    return node?.val || null;
}

function traverse(root, o1, o2) {
    if(!root || root.val == o1 || root.val == o2) return root;

    const left = traverse(root.left, o1, o2);
    const right = traverse(root.right, o1, o2);

    if(!left && !right) return null;
    if(!left) return right;
    if(!right) return left;
    return root;
}

module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};

思路：

这道题就是查找二叉树两个节点的最近公共祖先的通用解法，二叉树没说是二叉搜索树，所以不能用二叉搜索树的特性去搜索。

找公共祖先的通用解法： 后序遍历+回溯

function traverse(root, o1, o2) {
    // 递归终止条件
    if(!root || root.val == o1 || root.val == o2) return root;
    // 后续遍历
    const left = traverse(root.left, o1, o2);
    const right = traverse(root.right, o1, o2);
    // 处理中节点的时候，考虑下面几种情况：
    // 1. 左右子树都为空 不存在公共祖先
    // 2. 左子树为空，公共祖先在右子树
    // 3. 右子树为空，公共祖先在左子树
    // 4. o1,o2 出现在两边，那么此时root就为公共祖先
    if(!left && !right) return null;
    if(!left) return right;
    if(!right) return left;
    return root;
}