/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
function lowestCommonAncestor(root, p, q) {
    const node = travese(root, p, q);
    return node?.val || null; 
}

function travese(root, p, q) {
    /// 终止条件
    if (root == null || root.val == p || root.val == q) {
        return root;
    }

    // 后序遍历
    const left = travese(root.left, p, q);
    const right = travese(root.right, p, q);
    // 处理'中'结点
    if (left == null && right == null) {
        // 若未找到节点 p 或 q
        return null;
    } else if (left == null && right != null) {
        // 若找到一个节点
        return right;
    } else if (left != null && right == null) {
        // 若找到一个节点
        return left;
    } else {
        // 若找到两个节点
        return root;
    }
}

module.exports = {
    lowestCommonAncestor
};

思路1：

从 p，q 出发，从二叉树底层逐个往上找 p，q 的 公共祖先。

这种思路的搜索方式是从二叉树的低层往上查找，可是二叉树的解构最简单的是从根节点出发往下查找（也只能从上往下找）。我们利用了二叉树后序遍历结合回溯的思想达成了从树的底层往上查找的方式。

const left = traverse(root.left, p, q);
const right = traverse(root.right, p, q);
// 判断 中 节点的情况返回
...

在处理中节点 node 的时候，我们判断 p、q 在不在 node 的左右子树里面。

思路2：

根据二叉搜索树的特性，'' 二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值 ''，

从二叉树的根节点出发依次判断节点 node 和 p , q 的大小

function lowestCommonAncestor( root ,  p ,  q ) {
    const node = traverse(root, p, q);
    return node.val;
}

function traverse(root, p, q) {
    // p, q 在左边
    if(p < root.val && q < root.val) {
        return traverse(root.left, p, q);
    } 
    // p, q 在右边
    else if (p > root.val && q > root.val) {
        return traverse(root.right, p, q);
    }
    // 
    else {
        return root;
    }
}