235.二叉搜索树的最近公共祖先

/**
 * 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) {
    // 先找到p q的所有祖先节点
    function getGrands(root, n) {
        // 从根节点到该节点路径上的所有节点（包括自身），即为祖先节点集合
        let grands = []
        let cur = root
        while (cur) {
            grands.push(cur)
            if (n.val === cur.val) {
                return grands
            } else if (n.val < cur.val) {
                cur = cur.left
            } else if (n.val > cur.val) {
                cur = cur.right
            }
        }
        return []
    }

    let g1 = getGrands(root, p)
    let g2 = getGrands(root, q)
    console.log(g1.map(e => e.val), g2.map(e => e.val));
    // 找到最近的相同节点
    while (g1.length) {
        let node = g1.pop()
        for (let i = g2.length - 1; i >= 0; i--) {
            if (node.val === g2[i].val) {
                return node
            }
        }
    }
};