来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解答

比较傻的办法，性能也比较差：
使用层级遍历的方法，先把父节点都收集起来，然后比较两个数组

var lowestCommonAncestor = function(root, p, q) {
    let stack = [ root ];
    root.parents = [ root ];
    while (stack.length) {
        let temp = [];
        for (let item of stack) {
            if (item) {
                const leftNode = item?.left;
                if (leftNode) {
                    leftNode.parents = [...item.parents, leftNode];
                    temp.push(leftNode);
                }
                const rightNode = item?.right;
                if (rightNode) {
                    rightNode.parents = [...item.parents, rightNode];
                    temp.push(rightNode);
                }
            }
        }
        stack = temp;
    }
    let pParents = p.parents;
    let qParents = q.parents;
    let startIndex = 0;
    while (pParents[startIndex] && pParents[startIndex] === qParents[startIndex]) {
        startIndex++;
    }
    return pParents[startIndex - 1];
};

优化

1. 可以使用递归，递归中 return 使用 或||，因为走左还是走右不确定，只有匹配到才返回数组，否则碰到 null 则返回 null

2. 两个数组的比对，从后往前，碰到另一个数组中没有的则中断并返回

   var lowestCommonAncestor = function(root, p, q) {
    function dfs (node, target, selected) {
        if (node === target) {
            return [...selected, node];
        }
        if (node === null) {
            return null;
        }
        return dfs(node.left, target, [...selected, node]) || dfs(node.right, target, [...selected, node]);
    }
    let pParents = dfs(root, p, []);
    let qParents = dfs(root, q, []);
    for (let i = pParents.length - 1; i >= 0; i--) {
        if (~qParents.indexOf(pParents[i])) {
            return pParents[i];
        }
    }
   };