236.二叉树的最近公共祖先

/**
 * 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) {
    // 1.先找到p，q各自路径上的所有节点
    // 2.然后从路径上的节点找到最近公共祖先
    // 这种解法内存超了没通过！

    const pPath = findPath(root, p) // p的路径
    const qPath = findPath(root, q) // q的路径
    // console.log(pPath, qPath)

    // 最近公共祖先，从后往前遍历
    for (let i = pPath.length - 1; i >= 0; i--) {
        for (let j = qPath.length - 1; j >= 0; j--) {
            if (pPath[i].val === qPath[j].val) {
                return pPath[i]
            }
        }
    }
};

// 查找target节点的路径
function findPath(root, target, path) {
    path = path || []

    if (!root) { // 递归结束条件
        return null
    }

    path.push(root)
    if (root.val === target.val) {
        return path
    }

    const left = findPath(root.left, target, path.slice(0)) // 浅拷贝一下，否则就共用一个path了
    const right = findPath(root.right, target, path.slice(0))
    return left || right
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    // 哈希表记录父节点
    let map = new Map()

    function recordParent(parent, cur) {
        if (!cur) { // 递归结束条件
            return
        }
        map.set(cur, parent)
        recordParent(cur, cur.left)
        recordParent(cur, cur.right)
    }

    recordParent(null, root) // 根节点没有父节点，所以是null
    // console.log(map)

    let pPath = [] // p节点的路径
    let cur = p
    while (cur) {
        pPath.unshift(cur.val)
        cur = map.get(cur)
    }

    let qPath = [] // q节点的路径
    cur = q
    while (cur) {
        qPath.unshift(cur.val)
        cur = map.get(cur)
    }
    console.log(pPath, qPath)

    // 最近公共祖先，从后往前遍历
    for (let i = pPath.length - 1; i >= 0; i--) {
        for (let j = qPath.length - 1; j >= 0; j--) {
            if (pPath[i].val === qPath[j].val) {
                return pPath[i]
            }
        }
    }
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    // 哈希表记录父节点
    let map = new Map()

    function recordParent(parent, cur) {
        if (!cur) { // 递归结束条件
            return
        }
        map.set(cur, parent)
        recordParent(cur, cur.left)
        recordParent(cur, cur.right)
    }

    recordParent(null, root) // 根节点没有父节点，所以是null
    // console.log(map)

    let pPath = [] // p节点的路径
    let cur = p
    while (cur) {
        pPath.unshift(cur.val)
        cur = map.get(cur)
    }

    let pVisitedMap = new Map() // 记录p的祖先节点
    // p节点从最近的祖先节点开始访问
    while (p) {
        pVisitedMap.set(p, true) // 记录访问过的祖先节点
        p = map.get(p)
    }

    // q节点开始遍历祖先节点，找到pVisitedMap已经访问过的就是最近的祖先节点
    while (q) {
        if (pVisitedMap.has(q)) {
            return q
        }
        q = map.get(q)
    }
}