Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

      _______6______
     /              \\
  ___2__          ___8__
 /      \\        /      \\
0      _4       7       9
      /  \\
     3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

我的想法是，找到这个两个元素，并把从根节点到这两个元素的路记下来，这个路上第一个相同的元素就是最低的共同祖先。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    var findNode = function(root,node,record){
        if (root===null) {
            return false;
        }
        if (root===node) {
            record.push(root);
            return true;
        } 
        if (findNode(root.left,node,record)) {
            record.push(root);
            return true;
        }
        if (findNode(root.right,node,record)) {
            record.push(root);
            return true;
        }
    }
    if (root!==null&&p!==null&&q!==null) {
        if (p===q) {
            return q;
        }
        var record1 = [];
        var record2 = [];
        findNode(root,p,record1);
        findNode(root,q,record2);
        //console.log(record1);
        //console.log(record2);
        for (var i = 0; i<record1.length; i++) {
            for (var j = 0; j<record2.length; j++) {
                //console.log(record1[i]+"&&&"+record2[j]);
                if (record1[i]===record2[j]) {
                    return record1[i];
                }
            }
        }
    }
    
};

但是这个方法好慢的样子。。。暂时没有想到别的方法。